Submission #1310374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310374		orgiloogii	Rice Hub (IOI11_ricehub)	C++20	68 / 100	8 ms	1348 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
int besthub(int n, int m, int x[], long long b) {
    vector<long long> pref(n + 1);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + x[i];
    }
    int res = 0;
    int l = 1;
    for (int r = 1;r <= n;r++) {
        while (l <= r) {
            int mid = (l + r) / 2;

            //cout << pref[mid - 1] - pref[l - 1] << " "  << pref[r] - pref[mid] << " " <<
             //   x[mid - 1] * (mid - l) - (pref[mid - 1] - pref[l - 1]) << " " << (pref[r] - pref[mid]) - x[mid - 1] * (r - mid) << endl;

            if (x[mid - 1] * (mid - l) - (pref[mid - 1] - pref[l - 1]) + (pref[r] - pref[mid]) - x[mid - 1] * (r - mid) <= b) {
                break;
            }
            l++;
        }
        res = max(res, r - l + 1);
        //pref[r] - pref[mid];
    }
    return res;
}

/*int main() {
    int n = 5;
    int a[n] = {1, 2, 10, 12, 14};
    cout << besthub(n, 20, a, 6);
}*/

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