Submission #209729

#	Time	Username	Problem	Language	Result	Execution time	Memory
209729		my99n	Rice Hub (IOI11_ricehub)	C++14	100 / 100	25 ms	1532 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

int besthub(int n, int L, int x[], long long b){ 
    long long s[100100]; s[0] = x[0];
    for (int i = 1; i < n; i++) s[i] = 0;
    for (int i = 1; i < n; i++) s[i] = x[i]+s[i-1];
    int l = 0, r = 0, ans = 1;
    while (r < n) {
        int med = (l+r)/2;
        long long low = (long long)x[med]*(med-l) - (s[med-1]-s[l-1]);
        long long high = s[r]-s[med] - (long long)x[med]*(r-med);
        if (low + high <= b) ans = max(ans, r++-l+1);
        else l++;
    }
    return ans;
}

// int main () {
//     int n, l, b;
//     scanf("%d %d %d", &n, &l, &b);
//     int x[n];
//     for (int i = 0; i < n; i++) scanf("%d", &x[i]);
//     printf("%d", besthub(n, l, x, b));
// }

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