답안 #94654

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94654 2019-01-22T06:47:13 Z andy627 쌀 창고 (IOI11_ricehub) C++17
100 / 100
220 ms 2680 KB
#include <stdio.h>
#include <algorithm>
#define LL long long
using namespace std;

LL sum[111111];

int besthub(int R,int L,int X[],LL B){
	sum[0]=X[0];
	for(int i=1;i<R;i++) sum[i]=sum[i-1]+X[i];

	int ans=0;
	for(int i=0;i<R;i++){
		int s=1,e=L,m;

		while(s<=e){
			m=(s+e)>>1;
			int sidx=lower_bound(X,X+R,X[i]-m)-X;
			int eidx=upper_bound(X,X+R,X[i]+m)-X-1;

			if((sum[eidx]-sum[i])-(LL)X[i]*(eidx-i)+(LL)X[i]*(i-sidx)-((!i?0:sum[i-1])-(!sidx?0:sum[sidx-1]))<=B) s=m+1;
			else e=m-1;
		}

		int sidx=lower_bound(X,X+R,X[i]-e)-X;
		int eidx=upper_bound(X,X+R,X[i]+e)-X-1;

		int sidx2=lower_bound(X,X+R,X[i]-s)-X;
		int eidx2=upper_bound(X,X+R,X[i]+s)-X-1;

		LL res=(sum[eidx]-sum[i])-(LL)X[i]*(eidx-i)+(LL)X[i]*(i-sidx)-((!i?0:sum[i-1])-(!sidx?0:sum[sidx-1]));

		if(sidx!=sidx2) ans=max((LL)ans,eidx-sidx+1+min((LL)eidx2-eidx+sidx-sidx2,(B-res)/(X[i]-X[sidx2])));
		else if(eidx!=eidx2) ans=max((LL)ans,eidx-sidx+1+min((LL)eidx2-eidx+sidx-sidx2,(B-res)/(X[eidx2]-X[i])));
		else ans=max(ans,eidx-sidx+1);
	}

	return ans;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 292 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 252 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 252 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 2 ms 252 KB Output is correct
21 Correct 2 ms 376 KB Output is correct
22 Correct 2 ms 376 KB Output is correct
23 Correct 2 ms 256 KB Output is correct
24 Correct 2 ms 380 KB Output is correct
25 Correct 2 ms 376 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 376 KB Output is correct
28 Correct 2 ms 256 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 252 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 256 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Correct 2 ms 256 KB Output is correct
19 Correct 2 ms 256 KB Output is correct
20 Correct 3 ms 256 KB Output is correct
21 Correct 4 ms 376 KB Output is correct
22 Correct 4 ms 376 KB Output is correct
23 Correct 5 ms 376 KB Output is correct
24 Correct 19 ms 376 KB Output is correct
25 Correct 7 ms 376 KB Output is correct
26 Correct 8 ms 376 KB Output is correct
27 Correct 9 ms 376 KB Output is correct
28 Correct 10 ms 376 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 632 KB Output is correct
2 Correct 43 ms 632 KB Output is correct
3 Correct 156 ms 2680 KB Output is correct
4 Correct 220 ms 2624 KB Output is correct
5 Correct 53 ms 1272 KB Output is correct
6 Correct 54 ms 1192 KB Output is correct
7 Correct 105 ms 2332 KB Output is correct
8 Correct 116 ms 2296 KB Output is correct
9 Correct 60 ms 1144 KB Output is correct
10 Correct 61 ms 1144 KB Output is correct
11 Correct 152 ms 2640 KB Output is correct
12 Correct 207 ms 2552 KB Output is correct
13 Correct 110 ms 1272 KB Output is correct
14 Correct 112 ms 1328 KB Output is correct
15 Correct 115 ms 2044 KB Output is correct
16 Correct 154 ms 2040 KB Output is correct
17 Correct 136 ms 2296 KB Output is correct
18 Correct 186 ms 2400 KB Output is correct
19 Correct 145 ms 2552 KB Output is correct
20 Correct 199 ms 2552 KB Output is correct