Submission #5037

#	Time	Username	Problem	Language	Result	Execution time	Memory
5037		tncks0121	Rice Hub (IOI11_ricehub)	C++98	100 / 100	28 ms	6556 KiB

ricehub

#include<stdio.h>
 
typedef unsigned long long llu;
 
#define N_ 100000
int N; llu K; 
llu S[N_+1], D[N_+1];
int res;
#define sum(a,b) (S[b] - S[(a)-1])
 
typedef long long ll;

int besthub (int R, int L, int *X, ll B) {
    int i;
 
    N = R; K = B;
    for(i=1; i<=N; i++){
        D[i] = X[i-1];
        S[i] = S[i-1] + D[i];
    }
 
    for(i=1; i<=N; i++){
        int left=i, right=N;
        while(left <= right){
            int mid = (left+right)>>1;
            int x = (i+mid)>>1;
            llu val = (D[x]*(x-i) - sum(i,x-1)) + (sum(x+1, mid) - D[x] * (mid-x));
            if(val <= K){
                if(res < mid - i + 1) res = mid - i + 1;
                left = mid + 1;
            }else right = mid - 1;
        }
    }
 
    return res;
    return 0;
}

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