답안 #79073

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
79073 2018-10-11T03:17:23 Z Plurm 쌀 창고 (IOI11_ricehub) C++11
100 / 100
19 ms 15940 KB
#include "ricehub.h"
#include <deque>
using namespace std;

int besthub(int R, int L, int X[], long long B)
{
	int lo = 0;
	int hi = R;
	int mid;
	long long QS[R];
	QS[0] = X[0];
	for(int i = 1; i < R; i++){
		QS[i] = QS[i-1] + (long long)X[i];
	}
	while(lo < hi){
		mid = (lo + hi + 1)/2;
		int md = mid/2;
		int first = 0;
		long long s = QS[mid-1] - QS[mid/2] - (long long)(mid-mid/2-1)*X[mid/2] +
			(long long)(mid/2)*X[mid/2] - QS[mid/2-1];
		for(int i = mid; i < R; i++){
			md = (2*i - mid)/2;
			first = i-mid+1;
			s = min(s,QS[i] - QS[md] - (long long)(i-md)*X[md] + (long long)(md-first)*X[md] - QS[md-1] + QS[first-1]);
			//if(s == 1ll) printf("DBG %lld %d %d\n",s,mid,i);
		}
		if(s <= B){
			lo = mid;
		}else{
			hi = mid-1;
		}
	}
	return lo;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 2 ms 496 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 2 ms 540 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 2 ms 784 KB Output is correct
10 Correct 2 ms 784 KB Output is correct
11 Correct 2 ms 784 KB Output is correct
12 Correct 2 ms 784 KB Output is correct
13 Correct 2 ms 784 KB Output is correct
14 Correct 2 ms 784 KB Output is correct
15 Correct 2 ms 800 KB Output is correct
16 Correct 2 ms 800 KB Output is correct
17 Correct 2 ms 800 KB Output is correct
18 Correct 2 ms 800 KB Output is correct
19 Correct 2 ms 800 KB Output is correct
20 Correct 2 ms 800 KB Output is correct
21 Correct 2 ms 800 KB Output is correct
22 Correct 2 ms 800 KB Output is correct
23 Correct 2 ms 800 KB Output is correct
24 Correct 2 ms 800 KB Output is correct
25 Correct 2 ms 800 KB Output is correct
26 Correct 2 ms 800 KB Output is correct
27 Correct 2 ms 800 KB Output is correct
28 Correct 2 ms 800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 800 KB Output is correct
2 Correct 2 ms 800 KB Output is correct
3 Correct 2 ms 800 KB Output is correct
4 Correct 2 ms 800 KB Output is correct
5 Correct 2 ms 800 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 2 ms 800 KB Output is correct
8 Correct 2 ms 912 KB Output is correct
9 Correct 2 ms 912 KB Output is correct
10 Correct 2 ms 912 KB Output is correct
11 Correct 2 ms 1048 KB Output is correct
12 Correct 2 ms 1048 KB Output is correct
13 Correct 2 ms 1048 KB Output is correct
14 Correct 2 ms 1048 KB Output is correct
15 Correct 2 ms 1048 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1048 KB Output is correct
18 Correct 2 ms 1048 KB Output is correct
19 Correct 2 ms 1048 KB Output is correct
20 Correct 2 ms 1048 KB Output is correct
21 Correct 3 ms 1084 KB Output is correct
22 Correct 2 ms 1084 KB Output is correct
23 Correct 2 ms 1144 KB Output is correct
24 Correct 2 ms 1168 KB Output is correct
25 Correct 2 ms 1196 KB Output is correct
26 Correct 3 ms 1236 KB Output is correct
27 Correct 3 ms 1276 KB Output is correct
28 Correct 3 ms 1316 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1484 KB Output is correct
2 Correct 5 ms 1612 KB Output is correct
3 Correct 17 ms 3668 KB Output is correct
4 Correct 17 ms 4700 KB Output is correct
5 Correct 19 ms 4700 KB Output is correct
6 Correct 10 ms 4856 KB Output is correct
7 Correct 15 ms 6220 KB Output is correct
8 Correct 15 ms 6992 KB Output is correct
9 Correct 10 ms 6992 KB Output is correct
10 Correct 10 ms 6992 KB Output is correct
11 Correct 19 ms 8520 KB Output is correct
12 Correct 19 ms 9660 KB Output is correct
13 Correct 11 ms 9660 KB Output is correct
14 Correct 12 ms 9832 KB Output is correct
15 Correct 15 ms 10988 KB Output is correct
16 Correct 15 ms 11668 KB Output is correct
17 Correct 18 ms 12872 KB Output is correct
18 Correct 18 ms 13768 KB Output is correct
19 Correct 19 ms 14856 KB Output is correct
20 Correct 19 ms 15940 KB Output is correct