# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
5036 | 2014-01-29T04:26:09 Z | tncks0121 | Rice Hub (IOI11_ricehub) | C++ | 0 ms | 0 KB |
#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 = X; 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; }