Submission #1499205

---

Source Code Expand

#include <bits/stdc++.h>

#ifndef LOCAL_
#define fprintf if( false ) fprintf
#endif // LOCAL_
#define dump() fprintf(stderr, "#%s.%d\n", __func__, __LINE__);
#define dumpl(x1) fprintf(stderr, "#%s.%d (%s) = (%ld)\n", __func__, __LINE__, #x1, x1);
#define dumpll(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%ld, %ld)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define dumplll(x1, x2, x3) fprintf(stderr, "#%s.%d (%s, %s, %s) = (%ld, %ld, %ld)\n", __func__, __LINE__, #x1, #x2, #x3, x1, x2, x3);
#define dumpd(x1) fprintf(stderr, "#%s.%d (%s) = (%lf)\n", __func__, __LINE__, #x1, x1);
#define dumpdd(x1, x2) fprintf(stderr, "#%s.%d (%s, %s) = (%lf, %lf)\n", __func__, __LINE__, #x1, #x2, x1, x2);
#define loop for(;;)
typedef std::vector<long> LI;
typedef std::queue<long> QI;
#define rep(i,n) for(long i = 0; i < (long)n; ++i)
const double pi = M_PI;
const long mod = 1000000007;

template<typename T> void scan1(T& x) { fprintf(stderr, "unknown type\n"); }
template<> void scan1(long& x) { if( scanf("%ld", &x) < 0 ) exit(0); }
template<> void scan1(std::string& x) { if( not ( std::cin >> x ) ) exit(0); }
void scan() {}
template<typename Head, typename... Tail>
void scan(Head& x, Tail&... xs) {
  scan1(x); scan(xs...);
}

struct Solver {
   Solver() { fprintf(stderr, "--------Solver begin--------\n"); }
   ~Solver() { fprintf(stderr, "--------Solver end--------\n"); }
   long n, m;
   LI xs, ys;
   long memo[2048][2048];
   long f(long i, long k) {
      if( i < 0 or k < 0 ) return (1LL << 53);
      if( memo[i][k] >= 0 ) return memo[i][k];
      // dumpll(i, k);
      if( k <= 0 ) return 0;
      if( i == 0 ) {
         if( k == 0 ) return 0;
         else if( k == 1 ) return 1;
         else return (1LL << 53);
      }
      if( i < 0 ) return (1LL << 53);
      if( i + 1 < k ) return (1LL << 53);
      // not select
      long res = f(i-1, k);
      // select
      long t = f(i-1, k-1);
      // t / ys[i-1] < t + ? / ys[i]
      // ys[i] * t / ys[i-1] < (t + ?)
      // t * ys[i] / ys[i-1] - t < ?
      // t * ys[i] / ys[i-1] - t * ys[i-1] / ys[i-1] < ?
      // t * (ys[i] - ys[i-1]) / ys[i-1] < ?
      // t * (ys[i] - ys[i-1]) / ys[i-1] + 1
      dumpll(i, k);
      // long s = (t * (ys[i] - ys[i-1]) + (ys[i-1] - 1)) / ys[i-1];
      long s = t * (ys[i] - ys[i-1]) / ys[i-1] + 1;
      if( s <= xs[i] ) {
         dumpl(s);
         res = std::min(res, t + s);
      }
      return memo[i][k] = res;
   }
   void solve() {
      scan(n, m);
      xs.resize(n); for(long &x : xs) scan(x);
      for(long i = 0; i < 2048; ++i) {
         for(long k = 0; k < 2048; ++k) {
            memo[i][k] = -1;
         }
      }
      long t = 0;
      ys.resize(n);
      for(long i = 0; i < n; ++i) t += xs[i], ys[i] = t;
      if( ys[n-1] == m ) {
         puts("1");
         return;
      }
      long res = 0;
      for(long i = n; i >= 0; --i) {
         dumpll(i, f(n-1, i));
         if( f(n-1, i) <= m ) {
            printf("%ld\n", i);
            break;
         }
      }
   }
};

int main() {
   loop std::unique_ptr<Solver>(new Solver())->solve();
}

Submission Info

Judge Result