Submission #1248047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248047		nikd	Rice Hub (IOI11_ricehub)	C++20	17 / 100	0 ms	328 KiB

ricehub

#include <bits/stdc++.h>
#include <istream>
using namespace std;
using ll = long long;

ll besthub(int n, int l, int* x, ll b){
    int sol = 0;
    int idxl = 0;
    int idxr = 0;
    ll curr_cost = 0;
    while(idxr+1 < n && curr_cost+x[idxr+1]-x[0] <= b){
        curr_cost += x[idxr+1] - x[0];
        idxr++;
    }
    sol = idxr-idxl+1;
    for(int i = 1; i<n; i++){
        ll delta = x[i]-x[i-1];
        curr_cost += (i-idxl)*delta;
        curr_cost -= (idxr-i+1)*delta;
        if(idxr < i){
            assert(idxr+1 == i);
            //idxr++;
        }
        while(curr_cost > b){
            curr_cost -= x[i]-x[idxl];
            idxl++;
            assert(idxl <= i);
        }
        while(idxr+1 < n && curr_cost+x[idxr+1]-x[i] <= b){
            curr_cost += x[idxr+1] - x[i];
            idxr++;
        }
        while(idxr+1 < n && x[idxr+1]-x[i] < x[i]-x[idxl]){
            curr_cost -= x[i]-x[idxl];
            curr_cost += x[idxr+1]-x[i];
            idxl++; idxr++;
        }
        while(idxr+1 < n && curr_cost+x[idxr+1]-x[i] <= b){
            curr_cost += x[idxr+1] - x[i];
            idxr++;
        }
        sol = max(sol, idxr-idxl+1);
    }
    return sol;
}

// int main(){
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
//     int n; cin >> n;
//     ll b; cin >> b;
//     vector<ll> x(n);
//     for(ll &i: x) cin >> i;
//     cout << besthub(n, 0, x,b) << '\n';
// }

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32