oj.uz

답안 #132995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132995 2019-07-20T03:46:37 Z mirbek01 Candies (JOI18_candies) C++11
100 / 100
 1271 ms 29840 KB 
# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 3;

int n, a[N];
long long ans;
set < pair<long long, long long> > val, ind;

int main(){
	cin >> n;
	
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		val.insert( {a[i], i} );
		ind.insert( {i, a[i]} );
	}
	
	val.insert({-1e18, -1}), ind.insert({-1, -1e18});
	val.insert({-1e18, n + 1}), ind.insert({n + 1, -1e18});
	
	for(int i = 1; i <= (n + 1) / 2; i ++){
		auto it = -- val.end();
		ans += it->first;
		auto ps = ind.find({it->second, it->first});
		auto x = *prev(ps);
		auto y = *ps;
		auto z = *next(ps);
		for(auto it : {x, y, z}){
			ind.erase(it);
			val.erase({it.second, it.first});
		}
		ind.insert({y.first, x.second + z.second - y.second});
		val.insert({x.second + z.second - y.second, y.first});
		cout << ans << endl;
	}
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 9 ms 632 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 8 ms 636 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 8 ms 632 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 8 ms 632 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 9 ms 636 KB Output is correct
13 Correct 8 ms 632 KB Output is correct
14 Correct 8 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct
16 Correct 8 ms 632 KB Output is correct
17 Correct 8 ms 632 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 8 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 632 KB Output is correct
2 Correct 9 ms 632 KB Output is correct
3 Correct 8 ms 632 KB Output is correct
4 Correct 8 ms 636 KB Output is correct
5 Correct 8 ms 632 KB Output is correct
6 Correct 8 ms 632 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 8 ms 632 KB Output is correct
9 Correct 8 ms 632 KB Output is correct
10 Correct 8 ms 632 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 9 ms 636 KB Output is correct
13 Correct 8 ms 632 KB Output is correct
14 Correct 8 ms 632 KB Output is correct
15 Correct 8 ms 632 KB Output is correct
16 Correct 8 ms 632 KB Output is correct
17 Correct 8 ms 632 KB Output is correct
18 Correct 8 ms 632 KB Output is correct
19 Correct 8 ms 632 KB Output is correct
20 Correct 8 ms 632 KB Output is correct
21 Correct 1191 ms 29620 KB Output is correct
22 Correct 1271 ms 29536 KB Output is correct
23 Correct 1150 ms 29688 KB Output is correct
24 Correct 748 ms 29432 KB Output is correct
25 Correct 763 ms 29376 KB Output is correct
26 Correct 758 ms 29344 KB Output is correct
27 Correct 772 ms 29600 KB Output is correct
28 Correct 778 ms 29556 KB Output is correct
29 Correct 771 ms 29548 KB Output is correct
30 Correct 797 ms 29756 KB Output is correct
31 Correct 791 ms 29652 KB Output is correct
32 Correct 796 ms 29576 KB Output is correct
33 Correct 925 ms 29332 KB Output is correct
34 Correct 934 ms 29356 KB Output is correct
35 Correct 966 ms 29528 KB Output is correct
36 Correct 1170 ms 29600 KB Output is correct
37 Correct 1160 ms 29564 KB Output is correct
38 Correct 1187 ms 29652 KB Output is correct
39 Correct 758 ms 29404 KB Output is correct
40 Correct 754 ms 29396 KB Output is correct
41 Correct 756 ms 29560 KB Output is correct
42 Correct 773 ms 29616 KB Output is correct
43 Correct 771 ms 29748 KB Output is correct
44 Correct 769 ms 29840 KB Output is correct
45 Correct 789 ms 29628 KB Output is correct
46 Correct 787 ms 29708 KB Output is correct
47 Correct 782 ms 29652 KB Output is correct
48 Correct 919 ms 29404 KB Output is correct
49 Correct 937 ms 29364 KB Output is correct
50 Correct 923 ms 29400 KB Output is correct