Source Code
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, k, r, v[N], sum;

void scan(int &x, int l, int r) {
    assert(scanf("%d", &x) != -1);
    assert(x>=l && x<=r);
}

bool check(int d) {
    if(!d) return sum <= k;
    int cur = 0;
    int j = 0;
    while(j < d)
        cur += v[j++];
    int mx = cur;
    while(j < n) {
        cur += v[j] - v[j-d];
        mx = max(mx, cur);
        ++j;
    }
    return sum - mx + mx / r <= k;
}

int main() {
    scan(n, 1, 500);
    scan(k, 1, 1000000000);
    scan(r, 1, 1000000000);
    for(int i=0; i<n; ++i) {
        scan(v[i], 1, 10000);
        sum+=v[i];
    }
    int lo = 0, hi = n, md;
    while(lo<=hi) {
        md=(lo+hi)/2;
        if(check(md)) hi = md - 1;
        else lo = md + 1;
    }
    if(hi == n) puts("-1");
    else cout<<hi+1<<endl;
	return 0;
}
Copy
Mohannad and Calories Light
GNU G++17
3 ms
660 KB
Runtime Error