Submission #3017960

---

Source Code Expand

#include <iostream>
#include <vector>
#include <cmath>

using ll = long long;
using namespace std;
static const int INF = 1500000000;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> v(2, vector<int>(2001, INF));
    v[0][0] = 0;

    int bats = 0;
    for (int i = 1; i <= n; ++i) {
        int now = i % 2, prv = now^1;
        fill(v[now].begin(), v[now].end(), INF);
        int a;
        cin >> a;
        bats += a;
        v[now][0] = v[prv][0];
        for (int j = 1; j <= n; ++j) {

            v[now][j] = min(v[prv][j], v[now][j]);
            int wins = a * v[prv][j-1]/(bats-a > 0 ? bats-a : 1) + 1;
            if(v[prv][j-1] + wins <= k){
                v[now][j] = min(v[now][j], v[prv][j-1]+wins);
            }
        }
    }
    for (int i = n; i >= 0; --i) {
        if(k >= v[n%2][i]) {
            cout << (bats - k ? i : 1) << "\n";
            break;
        }
    }
    return 0;
}

Submission Info

Judge Result