Submission #506019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
506019	2022-01-11T11:55:22 Z	sidon	Candies (JOI18_candies)	C++17	8 / 100	5000 ms	10064 KB

candies

#include <bits/stdc++.h>
using namespace std;
#define Z 200'002

int64_t N, K, L[Z], R[Z], r[Z], A[Z], sum;
priority_queue<array<int64_t, 2>> pq;

int main() {
	cin >> N;

	for(int i = 1; i <= N; i++) {
		cin >> A[i];
		L[i] = i - 1, R[i] = i + 1;
		pq.push({A[i], i});
	}
 
	R[N+1] = N+1, L[N+1] = N;
	R[0] = r[0] = r[N+1] = 1;
 
	for(int k = 1; k*2 <= N+1; k++) {
		while(r[pq.top()[1]]) pq.pop();
		auto [v, i] = pq.top(); pq.pop();
 
		cout << (sum += v) << '\n';
		for(int j = 0; j < 2; j++, swap(L, R))
			r[L[i]] ? r[i]++ : v -= A[L[i]], r[L[i]] = 1, R[L[i] = L[L[i]]] = i;

		if(!r[i]) pq.push({A[i] = -v, i});
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	309 ms	3644 KB	Output is correct
2	Correct	330 ms	3504 KB	Output is correct
3	Correct	321 ms	3520 KB	Output is correct
4	Correct	297 ms	3760 KB	Output is correct
5	Correct	296 ms	3516 KB	Output is correct
6	Correct	349 ms	3512 KB	Output is correct
7	Correct	306 ms	3508 KB	Output is correct
8	Correct	313 ms	3520 KB	Output is correct
9	Correct	296 ms	3520 KB	Output is correct
10	Correct	342 ms	3512 KB	Output is correct
11	Correct	348 ms	3512 KB	Output is correct
12	Correct	320 ms	3520 KB	Output is correct
13	Correct	310 ms	3640 KB	Output is correct
14	Correct	295 ms	3524 KB	Output is correct
15	Correct	340 ms	3512 KB	Output is correct
16	Correct	296 ms	3520 KB	Output is correct
17	Correct	323 ms	3512 KB	Output is correct
18	Correct	306 ms	3640 KB	Output is correct
19	Correct	289 ms	3524 KB	Output is correct
20	Correct	289 ms	3524 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	309 ms	3644 KB	Output is correct
2	Correct	330 ms	3504 KB	Output is correct
3	Correct	321 ms	3520 KB	Output is correct
4	Correct	297 ms	3760 KB	Output is correct
5	Correct	296 ms	3516 KB	Output is correct
6	Correct	349 ms	3512 KB	Output is correct
7	Correct	306 ms	3508 KB	Output is correct
8	Correct	313 ms	3520 KB	Output is correct
9	Correct	296 ms	3520 KB	Output is correct
10	Correct	342 ms	3512 KB	Output is correct
11	Correct	348 ms	3512 KB	Output is correct
12	Correct	320 ms	3520 KB	Output is correct
13	Correct	310 ms	3640 KB	Output is correct
14	Correct	295 ms	3524 KB	Output is correct
15	Correct	340 ms	3512 KB	Output is correct
16	Correct	296 ms	3520 KB	Output is correct
17	Correct	323 ms	3512 KB	Output is correct
18	Correct	306 ms	3640 KB	Output is correct
19	Correct	289 ms	3524 KB	Output is correct
20	Correct	289 ms	3524 KB	Output is correct
21	Execution timed out	5079 ms	10064 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-