oj.uz

Submission #677563

# Submission time Handle Problem Language Result Execution time Memory
677563 2023-01-03T16:15:16 Z penguin133 Solar Storm (NOI20_solarstorm) C++17
100 / 100
 431 ms 207272 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
 
int n, s, A[1000005], B[1000005];
long long P[1000005], X[1000005], k;
pi pre[1000005];
int par[20][1000005];
vector<int> v[1000005];
bool vis[1000005];
void dfs(int x, int p){
	if(vis[x])return;
	vis[x] = 1;
	par[0][x] = p;
	for(auto i : v[x])dfs(i, x);
}
 
void solve(){
	cin >> n >> s >> k;
	for(int i=2;i<=n;i++)cin >> A[i], P[i] = P[i-1] + A[i];
	for(int i=1;i<=n;i++)cin >> B[i], X[i] = X[i-1] + B[i];
	for(int i=1;i<=n;i++){
		int lo = 1, hi = i, ans = hi;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(P[i] - P[mid] <= k)ans = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		lo = 1, hi = ans;
		int ans2 = ans;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			if(P[ans] - P[mid] <= k)ans2 = mid, hi = mid - 1;
			else lo = mid + 1;
		}
		v[ans2-1].push_back(i);
		pre[i] = {ans2 - 1, ans};
	}
	for(int i=0;i<n;i++)dfs(i, 0);
	for(int i=1;i<=19;i++)for(int j=1;j<=n;j++)par[i][j] = par[i-1][par[i-1][j]];
	int in = 0;
  long long mx = 0;
	for(int i=1;i<=n;i++){
		int tmp = i;
		for(int j=19;j>=0;j--){
			if(s >> j & 1)tmp = par[j][tmp];
			if(tmp == 0)break;
		}
		if(X[i] - X[tmp] > mx)mx = X[i] - X[tmp], in = i;
	}
	int bt = in, rem = s;
	vector<int> ans;
	while(rem && bt){
		rem--;
		ans.push_back(pre[bt].se);
		bt = pre[bt].fi;
	}
	//cout << mx << '\n';
	cout << (int)ans.size() << '\n';
	for(auto i : ans)cout << i << " ";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

SolarStorm.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 18 ms 25556 KB Output is correct
3 Correct 16 ms 25556 KB Output is correct
4 Correct 14 ms 24660 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 14 ms 24872 KB Output is correct
7 Correct 15 ms 25044 KB Output is correct
8 Correct 15 ms 25172 KB Output is correct
9 Correct 13 ms 24752 KB Output is correct
10 Correct 17 ms 25200 KB Output is correct
11 Correct 16 ms 25220 KB Output is correct
12 Correct 14 ms 24576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 122236 KB Output is correct
2 Correct 183 ms 90288 KB Output is correct
3 Correct 176 ms 103880 KB Output is correct
4 Correct 227 ms 115732 KB Output is correct
5 Correct 273 ms 131248 KB Output is correct
6 Correct 345 ms 166500 KB Output is correct
7 Correct 250 ms 123712 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 18 ms 25556 KB Output is correct
3 Correct 16 ms 25556 KB Output is correct
4 Correct 14 ms 24660 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 14 ms 24872 KB Output is correct
7 Correct 15 ms 25044 KB Output is correct
8 Correct 15 ms 25172 KB Output is correct
9 Correct 13 ms 24752 KB Output is correct
10 Correct 17 ms 25200 KB Output is correct
11 Correct 16 ms 25220 KB Output is correct
12 Correct 14 ms 24576 KB Output is correct
13 Correct 222 ms 122236 KB Output is correct
14 Correct 183 ms 90288 KB Output is correct
15 Correct 176 ms 103880 KB Output is correct
16 Correct 227 ms 115732 KB Output is correct
17 Correct 273 ms 131248 KB Output is correct
18 Correct 345 ms 166500 KB Output is correct
19 Correct 250 ms 123712 KB Output is correct
20 Correct 171 ms 87304 KB Output is correct
21 Correct 246 ms 136256 KB Output is correct
22 Correct 276 ms 156980 KB Output is correct
23 Correct 216 ms 118424 KB Output is correct
24 Correct 198 ms 109476 KB Output is correct
25 Correct 290 ms 117540 KB Output is correct
26 Correct 189 ms 91216 KB Output is correct
27 Correct 259 ms 114392 KB Output is correct
28 Correct 281 ms 114628 KB Output is correct
29 Correct 354 ms 141592 KB Output is correct
30 Correct 257 ms 125272 KB Output is correct
31 Correct 234 ms 121064 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 163816 KB Output is correct
2 Correct 205 ms 108468 KB Output is correct
3 Correct 164 ms 114704 KB Output is correct
4 Correct 285 ms 155240 KB Output is correct
5 Correct 226 ms 151308 KB Output is correct
6 Correct 246 ms 158932 KB Output is correct
7 Correct 353 ms 196560 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 18 ms 25556 KB Output is correct
3 Correct 16 ms 25556 KB Output is correct
4 Correct 14 ms 24660 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 14 ms 24872 KB Output is correct
7 Correct 15 ms 25044 KB Output is correct
8 Correct 15 ms 25172 KB Output is correct
9 Correct 13 ms 24752 KB Output is correct
10 Correct 17 ms 25200 KB Output is correct
11 Correct 16 ms 25220 KB Output is correct
12 Correct 14 ms 24576 KB Output is correct
13 Correct 17 ms 25100 KB Output is correct
14 Correct 16 ms 25100 KB Output is correct
15 Correct 17 ms 25080 KB Output is correct
16 Correct 16 ms 24724 KB Output is correct
17 Correct 16 ms 25312 KB Output is correct
18 Correct 17 ms 25684 KB Output is correct
19 Correct 15 ms 25352 KB Output is correct
20 Correct 15 ms 25172 KB Output is correct
21 Correct 17 ms 25876 KB Output is correct
22 Correct 20 ms 25724 KB Output is correct
23 Correct 16 ms 25300 KB Output is correct
24 Correct 20 ms 25172 KB Output is correct
25 Correct 19 ms 25300 KB Output is correct
26 Correct 17 ms 25508 KB Output is correct
27 Correct 15 ms 25224 KB Output is correct
28 Correct 15 ms 25320 KB Output is correct
29 Correct 15 ms 25300 KB Output is correct
30 Correct 16 ms 25172 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 18 ms 25556 KB Output is correct
3 Correct 16 ms 25556 KB Output is correct
4 Correct 14 ms 24660 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 14 ms 24872 KB Output is correct
7 Correct 15 ms 25044 KB Output is correct
8 Correct 15 ms 25172 KB Output is correct
9 Correct 13 ms 24752 KB Output is correct
10 Correct 17 ms 25200 KB Output is correct
11 Correct 16 ms 25220 KB Output is correct
12 Correct 14 ms 24576 KB Output is correct
13 Correct 222 ms 122236 KB Output is correct
14 Correct 183 ms 90288 KB Output is correct
15 Correct 176 ms 103880 KB Output is correct
16 Correct 227 ms 115732 KB Output is correct
17 Correct 273 ms 131248 KB Output is correct
18 Correct 345 ms 166500 KB Output is correct
19 Correct 250 ms 123712 KB Output is correct
20 Correct 171 ms 87304 KB Output is correct
21 Correct 246 ms 136256 KB Output is correct
22 Correct 276 ms 156980 KB Output is correct
23 Correct 216 ms 118424 KB Output is correct
24 Correct 198 ms 109476 KB Output is correct
25 Correct 290 ms 117540 KB Output is correct
26 Correct 189 ms 91216 KB Output is correct
27 Correct 259 ms 114392 KB Output is correct
28 Correct 281 ms 114628 KB Output is correct
29 Correct 354 ms 141592 KB Output is correct
30 Correct 257 ms 125272 KB Output is correct
31 Correct 234 ms 121064 KB Output is correct
32 Correct 235 ms 123904 KB Output is correct
33 Correct 226 ms 105864 KB Output is correct
34 Correct 355 ms 141872 KB Output is correct
35 Correct 211 ms 94992 KB Output is correct
36 Correct 219 ms 100284 KB Output is correct
37 Correct 258 ms 108688 KB Output is correct
38 Correct 336 ms 160304 KB Output is correct
39 Correct 253 ms 147276 KB Output is correct
40 Correct 357 ms 197060 KB Output is correct

Subtask #7
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23892 KB Output is correct
2 Correct 18 ms 25556 KB Output is correct
3 Correct 16 ms 25556 KB Output is correct
4 Correct 14 ms 24660 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 14 ms 24872 KB Output is correct
7 Correct 15 ms 25044 KB Output is correct
8 Correct 15 ms 25172 KB Output is correct
9 Correct 13 ms 24752 KB Output is correct
10 Correct 17 ms 25200 KB Output is correct
11 Correct 16 ms 25220 KB Output is correct
12 Correct 14 ms 24576 KB Output is correct
13 Correct 222 ms 122236 KB Output is correct
14 Correct 183 ms 90288 KB Output is correct
15 Correct 176 ms 103880 KB Output is correct
16 Correct 227 ms 115732 KB Output is correct
17 Correct 273 ms 131248 KB Output is correct
18 Correct 345 ms 166500 KB Output is correct
19 Correct 250 ms 123712 KB Output is correct
20 Correct 171 ms 87304 KB Output is correct
21 Correct 246 ms 136256 KB Output is correct
22 Correct 276 ms 156980 KB Output is correct
23 Correct 216 ms 118424 KB Output is correct
24 Correct 198 ms 109476 KB Output is correct
25 Correct 290 ms 117540 KB Output is correct
26 Correct 189 ms 91216 KB Output is correct
27 Correct 259 ms 114392 KB Output is correct
28 Correct 281 ms 114628 KB Output is correct
29 Correct 354 ms 141592 KB Output is correct
30 Correct 257 ms 125272 KB Output is correct
31 Correct 234 ms 121064 KB Output is correct
32 Correct 289 ms 163816 KB Output is correct
33 Correct 205 ms 108468 KB Output is correct
34 Correct 164 ms 114704 KB Output is correct
35 Correct 285 ms 155240 KB Output is correct
36 Correct 226 ms 151308 KB Output is correct
37 Correct 246 ms 158932 KB Output is correct
38 Correct 353 ms 196560 KB Output is correct
39 Correct 17 ms 25100 KB Output is correct
40 Correct 16 ms 25100 KB Output is correct
41 Correct 17 ms 25080 KB Output is correct
42 Correct 16 ms 24724 KB Output is correct
43 Correct 16 ms 25312 KB Output is correct
44 Correct 17 ms 25684 KB Output is correct
45 Correct 15 ms 25352 KB Output is correct
46 Correct 15 ms 25172 KB Output is correct
47 Correct 17 ms 25876 KB Output is correct
48 Correct 20 ms 25724 KB Output is correct
49 Correct 16 ms 25300 KB Output is correct
50 Correct 20 ms 25172 KB Output is correct
51 Correct 19 ms 25300 KB Output is correct
52 Correct 17 ms 25508 KB Output is correct
53 Correct 15 ms 25224 KB Output is correct
54 Correct 15 ms 25320 KB Output is correct
55 Correct 15 ms 25300 KB Output is correct
56 Correct 16 ms 25172 KB Output is correct
57 Correct 235 ms 123904 KB Output is correct
58 Correct 226 ms 105864 KB Output is correct
59 Correct 355 ms 141872 KB Output is correct
60 Correct 211 ms 94992 KB Output is correct
61 Correct 219 ms 100284 KB Output is correct
62 Correct 258 ms 108688 KB Output is correct
63 Correct 336 ms 160304 KB Output is correct
64 Correct 253 ms 147276 KB Output is correct
65 Correct 357 ms 197060 KB Output is correct
66 Correct 165 ms 98616 KB Output is correct
67 Correct 315 ms 171508 KB Output is correct
68 Correct 223 ms 127264 KB Output is correct
69 Correct 298 ms 160392 KB Output is correct
70 Correct 176 ms 101396 KB Output is correct
71 Correct 391 ms 157836 KB Output is correct
72 Correct 245 ms 110844 KB Output is correct
73 Correct 335 ms 136556 KB Output is correct
74 Correct 183 ms 104304 KB Output is correct
75 Correct 297 ms 168692 KB Output is correct
76 Correct 214 ms 127688 KB Output is correct
77 Correct 281 ms 129972 KB Output is correct
78 Correct 201 ms 123144 KB Output is correct
79 Correct 251 ms 151040 KB Output is correct
80 Correct 335 ms 181528 KB Output is correct
81 Correct 171 ms 98420 KB Output is correct
82 Correct 264 ms 123072 KB Output is correct
83 Correct 203 ms 94376 KB Output is correct
84 Correct 207 ms 100056 KB Output is correct
85 Correct 223 ms 95560 KB Output is correct
86 Correct 346 ms 147308 KB Output is correct
87 Correct 185 ms 101772 KB Output is correct
88 Correct 327 ms 146320 KB Output is correct
89 Correct 257 ms 151784 KB Output is correct
90 Correct 232 ms 140056 KB Output is correct
91 Correct 431 ms 207272 KB Output is correct
92 Correct 352 ms 197508 KB Output is correct
93 Correct 394 ms 201824 KB Output is correct
94 Correct 380 ms 201688 KB Output is correct
95 Correct 331 ms 143620 KB Output is correct
96 Correct 272 ms 119364 KB Output is correct
97 Correct 346 ms 154052 KB Output is correct
98 Correct 225 ms 115144 KB Output is correct
99 Correct 265 ms 146880 KB Output is correct
100 Correct 263 ms 144172 KB Output is correct