Submission #2554782

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <iomanip>
#include <numeric>
#include <functional>
#include <queue>
#include <tuple>
#include <map>

using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vb = vector<char>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;

template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T &t, const V &v) { t = v; }

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T &t, const V &v) {
    for (auto &e:t) fill_v(e, v);
}

#define REP(i, a, b) for (int i = a; i < (int)(b); i++)
#define RREP(i, a, b) for (int i = (int)(b) - 1; i >= a; i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define all(x) (x).begin(),(x).end()
#define iter(c) __typeof((c).begin())
#define tr(i, c) for (iter(c) i = (c).begin(); i != (c).end(); i++)
#define mp(a, b) make_pair(a,b)

#define fi first
#define sn second
#define decpii(p) p.fi--,p.sn--;


#ifdef LOCAL
#define dump(c) cerr << "> " << #c << " = " << (c) << endl;
#define dumpn(c) cerr << "> " << #c << " = " << (c) << ", ";
#else
#define dump(c) ;
#define dumpn(c) ;
#endif


template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    return os << '(' << p.first << ',' << p.second << ')';
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a) {
    os << '[';
    rep(i, (int) a.size())os << (i ? " " : "") << a[i];
    return os << ']';
}


const int INF = 1 << 29;
const ll LINF = 1ll << 60;
const int MOD = 1000000007;

int dxf[] = {1, 0, -1, 0};
int dyf[] = {0, -1, 0, 1};

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

inline vi uni(vi &vec) {
    sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
    return vec;
}

struct ____ {
    ____() {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} ________;


auto solve() {
    int N, K;
    cin >> N >> K;
    vi a(N);
    rep(i, N) cin >> a[i];
    vll total(N + 1, 0);
    REP(i, 1, N + 1)total[i] = total[i - 1] + a[i - 1];

    if (K ==  accumulate(all(a), 0ll)) return 1;

    vvll dp(N + 1, vll(N + 1, LINF));
    dp[0][0] = 0;
    rep(i, N) {
        dump(i);
        rep(j, N + 1) {
            if (dp[i][j] == LINF) continue;
            chmin(dp[i + 1][j], dp[i][j]);
            double prev = 0.0;
            if (total[i] != 0)
                prev = (double) dp[i][j] / total[i];

            ll need = prev * total[i + 1];
            if ((double) need / total[i + 1] <= prev)
                need++;

            dumpn(j);
            dumpn(prev);
            dumpn(dp[i][j]);
            dumpn(total[i]);
            dumpn(need);
            dumpn(total[i + 1]);

            if (need <= K && need <= total[i + 1]) {
                chmin(dp[i + 1][j + 1], need);
                dump("OK")
            } else {
                dump("NG")
            }
        }
        dump(dp[i]);
    }

    rrep(i, N + 1) if (dp[N][i] != LINF) return i;
    return 0;
}


int main() {
//    cout << (solve() ? "yes" : "no") << endl;
    cout << solve() << endl;
//    solve();
    return 0;
}

Submission Info

Judge Result