oj.uz

답안 #211246

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211246 2020-03-19T18:09:33 Z socho Solar Storm (NOI20_solarstorm) C++14
100 / 100
 1494 ms 246120 KB 
#include "bits/stdc++.h"
using namespace std;

const int MXN = 1000005, MXK = 22;

long long n, s, k;
long long pf[MXN];

vector<int> subs[MXN];

int par[MXN][MXK];
int depth[MXN];

void dfs_decomp(int node, int last, int dep) {
	depth[node] = dep;
	par[node][0] = last;
	for (int i=1; i<MXK; i++) {
		int ab = par[node][i-1];
		if (ab != -1) {
			par[node][i] = par[ab][i-1];
		}
	}
	for (int i=0; i<subs[node].size(); i++) {
		if (subs[node][i] == last) continue;
		dfs_decomp(subs[node][i], node, dep+1);
	}
}

int kth_parent(int n, int k) {
	k = min(k, depth[n]);
	for (int i=0; i<MXK; i++) {
		if ((1 << i) & k) {
			n = par[n][i];
		}
	}
	return n;
}

void setup() {
	for (int i=0; i<MXN; i++) for (int j=0; j<MXK; j++) par[i][j] = -1;
	// dfs_depth(n, -1);
	dfs_decomp(n, -1, 0);
}

long long gpf(int a) {
	if (a < 0) return 0;
	return pf[a];
}

int main() {

	cin >> n >> s >> k;
	long long ad[n-1];
	for (int i=0; i<n-1; i++) cin >> ad[i];
	
	long long tr[n];
	tr[0] = 0;
	for (int i=1; i<n; i++) tr[i] = tr[i-1] + ad[i-1];
	
	long long val[n];
	for (int i=0; i<n; i++) cin >> val[i];
	partial_sum(val, val+n, pf);
	
	long long go[n];
	memset(go, 0, sizeof go);
	int with[n];
	
	for (int i=0; i<n; i++) {
		// if i placed one here
		long long lb = lower_bound(tr, tr+n, tr[i]-k) - tr;
		long long rb = upper_bound(tr, tr+n, tr[i]+k) - tr - 1;
		go[lb] = rb;
		with[lb] = i+1;
	}
	
	for (int i=1; i<n; i++) {
		if (go[i-1] > go[i]) {
			with[i] = with[i-1];
		}
		go[i] = max(go[i], go[i-1]);
	}
	
	for (int i=0; i<n; i++) {
		go[i]++;
		// cout << i << ' ' << go[i] << endl;
		subs[go[i]].push_back(i);
	}
	
	setup();
	
	long long best = 0;
	int at = 0;
	
	for (int i=0; i<n; i++) {
		long long score = gpf(kth_parent(i, s)-1) - gpf(i-1);
		if (score > best) {
			best = score;
			at = i;
		}
	}
	
	// cout << at << endl;
	
	bool can = true;
	int curr = at;
	vector<int> need;
	for (int i=0; i<s && can; i++) {
		need.push_back(with[curr]);
		// cout << curr << endl;
		curr = go[curr];
		if (curr >= n) can = false;
	}
	
	cout << need.size() << endl;
	for (int i=0; i<need.size(); i++) {
		cout << need[i] << ' ';
	}
	cout << endl;
	
}

Compilation message

SolarStorm.cpp: In function 'void dfs_decomp(int, int, int)':
SolarStorm.cpp:23:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<subs[node].size(); i++) {
                ~^~~~~~~~~~~~~~~~~~
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:115:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<need.size(); i++) {
                ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 109944 KB Output is correct
2 Correct 83 ms 110968 KB Output is correct
3 Correct 84 ms 111096 KB Output is correct
4 Correct 81 ms 110456 KB Output is correct
5 Correct 76 ms 109944 KB Output is correct
6 Correct 78 ms 110328 KB Output is correct
7 Correct 80 ms 110456 KB Output is correct
8 Correct 77 ms 110456 KB Output is correct
9 Correct 80 ms 110328 KB Output is correct
10 Correct 82 ms 110584 KB Output is correct
11 Correct 82 ms 110584 KB Output is correct
12 Correct 72 ms 110456 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 742 ms 153732 KB Output is correct
2 Correct 520 ms 140388 KB Output is correct
3 Correct 569 ms 151400 KB Output is correct
4 Correct 694 ms 159864 KB Output is correct
5 Correct 831 ms 168444 KB Output is correct
6 Correct 1145 ms 188236 KB Output is correct
7 Correct 886 ms 171896 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 109944 KB Output is correct
2 Correct 83 ms 110968 KB Output is correct
3 Correct 84 ms 111096 KB Output is correct
4 Correct 81 ms 110456 KB Output is correct
5 Correct 76 ms 109944 KB Output is correct
6 Correct 78 ms 110328 KB Output is correct
7 Correct 80 ms 110456 KB Output is correct
8 Correct 77 ms 110456 KB Output is correct
9 Correct 80 ms 110328 KB Output is correct
10 Correct 82 ms 110584 KB Output is correct
11 Correct 82 ms 110584 KB Output is correct
12 Correct 72 ms 110456 KB Output is correct
13 Correct 742 ms 153732 KB Output is correct
14 Correct 520 ms 140388 KB Output is correct
15 Correct 569 ms 151400 KB Output is correct
16 Correct 694 ms 159864 KB Output is correct
17 Correct 831 ms 168444 KB Output is correct
18 Correct 1145 ms 188236 KB Output is correct
19 Correct 886 ms 171896 KB Output is correct
20 Correct 650 ms 137820 KB Output is correct
21 Correct 903 ms 193528 KB Output is correct
22 Correct 1067 ms 209104 KB Output is correct
23 Correct 823 ms 151520 KB Output is correct
24 Correct 831 ms 147552 KB Output is correct
25 Correct 916 ms 155840 KB Output is correct
26 Correct 680 ms 141540 KB Output is correct
27 Correct 888 ms 154608 KB Output is correct
28 Correct 943 ms 155256 KB Output is correct
29 Correct 1222 ms 169260 KB Output is correct
30 Correct 1122 ms 167860 KB Output is correct
31 Correct 1006 ms 174224 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 986 ms 216644 KB Output is correct
2 Correct 596 ms 173468 KB Output is correct
3 Correct 623 ms 178072 KB Output is correct
4 Correct 883 ms 208632 KB Output is correct
5 Correct 851 ms 205696 KB Output is correct
6 Correct 891 ms 211320 KB Output is correct
7 Correct 1204 ms 241128 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 109944 KB Output is correct
2 Correct 83 ms 110968 KB Output is correct
3 Correct 84 ms 111096 KB Output is correct
4 Correct 81 ms 110456 KB Output is correct
5 Correct 76 ms 109944 KB Output is correct
6 Correct 78 ms 110328 KB Output is correct
7 Correct 80 ms 110456 KB Output is correct
8 Correct 77 ms 110456 KB Output is correct
9 Correct 80 ms 110328 KB Output is correct
10 Correct 82 ms 110584 KB Output is correct
11 Correct 82 ms 110584 KB Output is correct
12 Correct 72 ms 110456 KB Output is correct
13 Correct 93 ms 110456 KB Output is correct
14 Correct 86 ms 110456 KB Output is correct
15 Correct 78 ms 110456 KB Output is correct
16 Correct 80 ms 110328 KB Output is correct
17 Correct 84 ms 110840 KB Output is correct
18 Correct 118 ms 111096 KB Output is correct
19 Correct 86 ms 110840 KB Output is correct
20 Correct 92 ms 110712 KB Output is correct
21 Correct 84 ms 111308 KB Output is correct
22 Correct 88 ms 111096 KB Output is correct
23 Correct 109 ms 110584 KB Output is correct
24 Correct 82 ms 110456 KB Output is correct
25 Correct 80 ms 110712 KB Output is correct
26 Correct 83 ms 110968 KB Output is correct
27 Correct 100 ms 110840 KB Output is correct
28 Correct 80 ms 110892 KB Output is correct
29 Correct 80 ms 110840 KB Output is correct
30 Correct 99 ms 110456 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 109944 KB Output is correct
2 Correct 83 ms 110968 KB Output is correct
3 Correct 84 ms 111096 KB Output is correct
4 Correct 81 ms 110456 KB Output is correct
5 Correct 76 ms 109944 KB Output is correct
6 Correct 78 ms 110328 KB Output is correct
7 Correct 80 ms 110456 KB Output is correct
8 Correct 77 ms 110456 KB Output is correct
9 Correct 80 ms 110328 KB Output is correct
10 Correct 82 ms 110584 KB Output is correct
11 Correct 82 ms 110584 KB Output is correct
12 Correct 72 ms 110456 KB Output is correct
13 Correct 742 ms 153732 KB Output is correct
14 Correct 520 ms 140388 KB Output is correct
15 Correct 569 ms 151400 KB Output is correct
16 Correct 694 ms 159864 KB Output is correct
17 Correct 831 ms 168444 KB Output is correct
18 Correct 1145 ms 188236 KB Output is correct
19 Correct 886 ms 171896 KB Output is correct
20 Correct 650 ms 137820 KB Output is correct
21 Correct 903 ms 193528 KB Output is correct
22 Correct 1067 ms 209104 KB Output is correct
23 Correct 823 ms 151520 KB Output is correct
24 Correct 831 ms 147552 KB Output is correct
25 Correct 916 ms 155840 KB Output is correct
26 Correct 680 ms 141540 KB Output is correct
27 Correct 888 ms 154608 KB Output is correct
28 Correct 943 ms 155256 KB Output is correct
29 Correct 1222 ms 169260 KB Output is correct
30 Correct 1122 ms 167860 KB Output is correct
31 Correct 1006 ms 174224 KB Output is correct
32 Correct 1016 ms 154404 KB Output is correct
33 Correct 829 ms 149476 KB Output is correct
34 Correct 1198 ms 169624 KB Output is correct
35 Correct 764 ms 145696 KB Output is correct
36 Correct 825 ms 148604 KB Output is correct
37 Correct 927 ms 153552 KB Output is correct
38 Correct 1494 ms 193032 KB Output is correct
39 Correct 1014 ms 201972 KB Output is correct
40 Correct 1367 ms 235384 KB Output is correct

Subtask #7
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 109944 KB Output is correct
2 Correct 83 ms 110968 KB Output is correct
3 Correct 84 ms 111096 KB Output is correct
4 Correct 81 ms 110456 KB Output is correct
5 Correct 76 ms 109944 KB Output is correct
6 Correct 78 ms 110328 KB Output is correct
7 Correct 80 ms 110456 KB Output is correct
8 Correct 77 ms 110456 KB Output is correct
9 Correct 80 ms 110328 KB Output is correct
10 Correct 82 ms 110584 KB Output is correct
11 Correct 82 ms 110584 KB Output is correct
12 Correct 72 ms 110456 KB Output is correct
13 Correct 742 ms 153732 KB Output is correct
14 Correct 520 ms 140388 KB Output is correct
15 Correct 569 ms 151400 KB Output is correct
16 Correct 694 ms 159864 KB Output is correct
17 Correct 831 ms 168444 KB Output is correct
18 Correct 1145 ms 188236 KB Output is correct
19 Correct 886 ms 171896 KB Output is correct
20 Correct 650 ms 137820 KB Output is correct
21 Correct 903 ms 193528 KB Output is correct
22 Correct 1067 ms 209104 KB Output is correct
23 Correct 823 ms 151520 KB Output is correct
24 Correct 831 ms 147552 KB Output is correct
25 Correct 916 ms 155840 KB Output is correct
26 Correct 680 ms 141540 KB Output is correct
27 Correct 888 ms 154608 KB Output is correct
28 Correct 943 ms 155256 KB Output is correct
29 Correct 1222 ms 169260 KB Output is correct
30 Correct 1122 ms 167860 KB Output is correct
31 Correct 1006 ms 174224 KB Output is correct
32 Correct 986 ms 216644 KB Output is correct
33 Correct 596 ms 173468 KB Output is correct
34 Correct 623 ms 178072 KB Output is correct
35 Correct 883 ms 208632 KB Output is correct
36 Correct 851 ms 205696 KB Output is correct
37 Correct 891 ms 211320 KB Output is correct
38 Correct 1204 ms 241128 KB Output is correct
39 Correct 93 ms 110456 KB Output is correct
40 Correct 86 ms 110456 KB Output is correct
41 Correct 78 ms 110456 KB Output is correct
42 Correct 80 ms 110328 KB Output is correct
43 Correct 84 ms 110840 KB Output is correct
44 Correct 118 ms 111096 KB Output is correct
45 Correct 86 ms 110840 KB Output is correct
46 Correct 92 ms 110712 KB Output is correct
47 Correct 84 ms 111308 KB Output is correct
48 Correct 88 ms 111096 KB Output is correct
49 Correct 109 ms 110584 KB Output is correct
50 Correct 82 ms 110456 KB Output is correct
51 Correct 80 ms 110712 KB Output is correct
52 Correct 83 ms 110968 KB Output is correct
53 Correct 100 ms 110840 KB Output is correct
54 Correct 80 ms 110892 KB Output is correct
55 Correct 80 ms 110840 KB Output is correct
56 Correct 99 ms 110456 KB Output is correct
57 Correct 1016 ms 154404 KB Output is correct
58 Correct 829 ms 149476 KB Output is correct
59 Correct 1198 ms 169624 KB Output is correct
60 Correct 764 ms 145696 KB Output is correct
61 Correct 825 ms 148604 KB Output is correct
62 Correct 927 ms 153552 KB Output is correct
63 Correct 1494 ms 193032 KB Output is correct
64 Correct 1014 ms 201972 KB Output is correct
65 Correct 1367 ms 235384 KB Output is correct
66 Correct 693 ms 140480 KB Output is correct
67 Correct 1175 ms 217060 KB Output is correct
68 Correct 840 ms 184156 KB Output is correct
69 Correct 1075 ms 208240 KB Output is correct
70 Correct 719 ms 141760 KB Output is correct
71 Correct 1279 ms 174672 KB Output is correct
72 Correct 857 ms 150776 KB Output is correct
73 Correct 1199 ms 164728 KB Output is correct
74 Correct 763 ms 158712 KB Output is correct
75 Correct 1213 ms 212628 KB Output is correct
76 Correct 789 ms 183032 KB Output is correct
77 Correct 997 ms 159984 KB Output is correct
78 Correct 778 ms 179832 KB Output is correct
79 Correct 986 ms 200792 KB Output is correct
80 Correct 1257 ms 223608 KB Output is correct
81 Correct 683 ms 140468 KB Output is correct
82 Correct 929 ms 154960 KB Output is correct
83 Correct 671 ms 142584 KB Output is correct
84 Correct 745 ms 145528 KB Output is correct
85 Correct 727 ms 143372 KB Output is correct
86 Correct 1231 ms 170548 KB Output is correct
87 Correct 820 ms 155000 KB Output is correct
88 Correct 1192 ms 168944 KB Output is correct
89 Correct 991 ms 200952 KB Output is correct
90 Correct 909 ms 192376 KB Output is correct
91 Correct 1478 ms 246120 KB Output is correct
92 Correct 1354 ms 236148 KB Output is correct
93 Correct 1455 ms 241000 KB Output is correct
94 Correct 1438 ms 241256 KB Output is correct
95 Correct 1151 ms 167968 KB Output is correct
96 Correct 933 ms 155512 KB Output is correct
97 Correct 1397 ms 177012 KB Output is correct
98 Correct 1020 ms 161616 KB Output is correct
99 Correct 1070 ms 199396 KB Output is correct
100 Correct 1000 ms 197980 KB Output is correct