답안 #760621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
760621	2023-06-18T03:25:52 Z	SanguineChameleon	쌀 창고 (IOI11_ricehub)	C++17	100 / 100	160 ms	2920 KB

ricehub

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

const int maxN = 1e5 + 20;
int a[maxN];
long long pref[maxN];

int besthub(int N, int L, int X[], long long B) {
	for (int i = 1; i <= N; i++) {
		a[i] = X[i - 1];
		pref[i] = pref[i - 1] + a[i];
	}
	int res = 0;
	for (int i = 1; i <= N; i++) {
		int lt = 0;
		int rt = L;
		int lim = -1;
		int cnt = -1;
		long long cost = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			int li = lower_bound(a + 1, a + N + 1, a[i] - mt) - a;
			int ri = upper_bound(a + 1, a + N + 1, a[i] + mt) - a - 1;
			long long cost_l = 1LL * a[i] * (i - li) - (pref[i - 1] - pref[li - 1]);
			long long cost_r = (pref[ri] - pref[i]) - 1LL * a[i] * (ri - i);
			if (cost_l + cost_r <= B) {
				cost = cost_l + cost_r;
				cnt = ri - li + 1;
				lim = mt;
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		if (lim < L) {
			cnt += (B - cost) / (lim + 1);
		}
		res = max(res, cnt);
	}
	return res;
}

Subtask #1

17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct

Subtask #2

25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	312 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Correct	0 ms	212 KB	Output is correct
18	Correct	0 ms	212 KB	Output is correct
19	Correct	0 ms	212 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 ms	212 KB	Output is correct
22	Correct	1 ms	212 KB	Output is correct
23	Correct	1 ms	212 KB	Output is correct
24	Correct	1 ms	212 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	212 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	212 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1 ms	340 KB	Output is correct
19	Correct	2 ms	340 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	2 ms	340 KB	Output is correct
22	Correct	2 ms	320 KB	Output is correct
23	Correct	2 ms	356 KB	Output is correct
24	Correct	4 ms	324 KB	Output is correct
25	Correct	4 ms	320 KB	Output is correct
26	Correct	5 ms	340 KB	Output is correct
27	Correct	6 ms	444 KB	Output is correct
28	Correct	6 ms	340 KB	Output is correct

Subtask #4

32.0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	30 ms	596 KB	Output is correct
2	Correct	33 ms	624 KB	Output is correct
3	Correct	107 ms	1868 KB	Output is correct
4	Correct	160 ms	1856 KB	Output is correct
5	Correct	36 ms	1100 KB	Output is correct
6	Correct	36 ms	1428 KB	Output is correct
7	Correct	68 ms	2556 KB	Output is correct
8	Correct	76 ms	2636 KB	Output is correct
9	Correct	41 ms	1380 KB	Output is correct
10	Correct	39 ms	1364 KB	Output is correct
11	Correct	111 ms	2920 KB	Output is correct
12	Correct	143 ms	2920 KB	Output is correct
13	Correct	78 ms	1492 KB	Output is correct
14	Correct	78 ms	1472 KB	Output is correct
15	Correct	79 ms	2236 KB	Output is correct
16	Correct	107 ms	2260 KB	Output is correct
17	Correct	91 ms	2644 KB	Output is correct
18	Correct	129 ms	2636 KB	Output is correct
19	Correct	102 ms	2772 KB	Output is correct
20	Correct	139 ms	2792 KB	Output is correct