Submission #1260403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260403		torment	Rice Hub (IOI11_ricehub)	C++20	100 / 100	8 ms	1864 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <vector>
using namespace std;
int besthub(int n, int L, int x[], long long b){
    vector<int>X(n + 1);
    vector<long long>pref(n + 1);
    for(int i = 0;i < n;++i){
        X[i + 1] = x[i];
        pref[i + 1] = pref[i] + x[i];
    }
    int l = 1, r = n, ans = 1;
    while(l <= r){
        int mid = (l + r) / 2;
        long long mn = 1e18;
        for(int i = 1;i + mid - 1 <= n;++i){
            int j = i + mid - 1;
            int m = (i + j) / 2;
            long long cost = (m - i + 1ll) * X[m] - (pref[m] - pref[i - 1]) + (pref[j] - pref[m]) - (j - m) * 1ll * X[m];
            mn = min(mn, cost);
        }
        if(mn <= b){
            l = mid + 1;
            ans = mid;
        }
        else{
            r = mid - 1;
        }
    }
    return ans;
}
// int main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     int n, L;
//     long long b;
//     cin >> n >> L >> b;
//     int x[n];
//     for(int i = 0;i < n;++i){
//         cin >> x[i];
//     }
//     cout << besthub(n, L, x, b) << '\n';
// }

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