oj.uz

Submission #677560

# Submission time Handle Problem Language Result Execution time Memory
677560 2023-01-03T16:11:32 Z penguin133 Solar Storm (NOI20_solarstorm) C++17
46 / 100
 453 ms 262144 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, k, A[1000005], B[1000005], P[1000005], X[1000005], dp[1000005];
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, 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:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 26400 KB Output is correct
3 Correct 15 ms 26708 KB Output is correct
4 Correct 13 ms 25180 KB Output is correct
5 Correct 13 ms 23956 KB Output is correct
6 Correct 13 ms 25748 KB Output is correct
7 Correct 16 ms 26004 KB Output is correct
8 Correct 14 ms 26324 KB Output is correct
9 Correct 14 ms 25484 KB Output is correct
10 Correct 14 ms 26236 KB Output is correct
11 Correct 16 ms 26268 KB Output is correct
12 Correct 13 ms 25108 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 210084 KB Output is correct
2 Correct 160 ms 143680 KB Output is correct
3 Correct 198 ms 161484 KB Output is correct
4 Correct 268 ms 177800 KB Output is correct
5 Correct 294 ms 203656 KB Output is correct
6 Correct 423 ms 262144 KB Output is correct
7 Correct 224 ms 188752 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 26400 KB Output is correct
3 Correct 15 ms 26708 KB Output is correct
4 Correct 13 ms 25180 KB Output is correct
5 Correct 13 ms 23956 KB Output is correct
6 Correct 13 ms 25748 KB Output is correct
7 Correct 16 ms 26004 KB Output is correct
8 Correct 14 ms 26324 KB Output is correct
9 Correct 14 ms 25484 KB Output is correct
10 Correct 14 ms 26236 KB Output is correct
11 Correct 16 ms 26268 KB Output is correct
12 Correct 13 ms 25108 KB Output is correct
13 Correct 232 ms 210084 KB Output is correct
14 Correct 160 ms 143680 KB Output is correct
15 Correct 198 ms 161484 KB Output is correct
16 Correct 268 ms 177800 KB Output is correct
17 Correct 294 ms 203656 KB Output is correct
18 Correct 423 ms 262144 KB Output is correct
19 Correct 224 ms 188752 KB Output is correct
20 Correct 189 ms 143088 KB Output is correct
21 Correct 253 ms 203648 KB Output is correct
22 Correct 298 ms 236700 KB Output is correct
23 Correct 230 ms 200976 KB Output is correct
24 Correct 245 ms 184096 KB Output is correct
25 Correct 321 ms 191200 KB Output is correct
26 Correct 206 ms 146976 KB Output is correct
27 Correct 278 ms 184572 KB Output is correct
28 Correct 289 ms 183884 KB Output is correct
29 Correct 369 ms 230992 KB Output is correct
30 Correct 286 ms 199980 KB Output is correct
31 Correct 254 ms 187012 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 247076 KB Output is correct
2 Correct 208 ms 159588 KB Output is correct
3 Correct 192 ms 169548 KB Output is correct
4 Correct 327 ms 235648 KB Output is correct
5 Correct 264 ms 229256 KB Output is correct
6 Correct 279 ms 241568 KB Output is correct
7 Runtime error 342 ms 262144 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 26400 KB Output is correct
3 Correct 15 ms 26708 KB Output is correct
4 Correct 13 ms 25180 KB Output is correct
5 Correct 13 ms 23956 KB Output is correct
6 Correct 13 ms 25748 KB Output is correct
7 Correct 16 ms 26004 KB Output is correct
8 Correct 14 ms 26324 KB Output is correct
9 Correct 14 ms 25484 KB Output is correct
10 Correct 14 ms 26236 KB Output is correct
11 Correct 16 ms 26268 KB Output is correct
12 Correct 13 ms 25108 KB Output is correct
13 Correct 15 ms 26256 KB Output is correct
14 Correct 15 ms 25812 KB Output is correct
15 Correct 15 ms 25744 KB Output is correct
16 Correct 17 ms 25236 KB Output is correct
17 Correct 17 ms 25948 KB Output is correct
18 Correct 19 ms 26520 KB Output is correct
19 Correct 17 ms 26180 KB Output is correct
20 Correct 17 ms 25812 KB Output is correct
21 Correct 21 ms 26928 KB Output is correct
22 Correct 20 ms 26776 KB Output is correct
23 Correct 17 ms 26196 KB Output is correct
24 Correct 17 ms 25936 KB Output is correct
25 Correct 19 ms 26200 KB Output is correct
26 Correct 17 ms 26388 KB Output is correct
27 Correct 16 ms 25876 KB Output is correct
28 Correct 18 ms 25956 KB Output is correct
29 Correct 17 ms 25940 KB Output is correct
30 Correct 16 ms 26196 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 26400 KB Output is correct
3 Correct 15 ms 26708 KB Output is correct
4 Correct 13 ms 25180 KB Output is correct
5 Correct 13 ms 23956 KB Output is correct
6 Correct 13 ms 25748 KB Output is correct
7 Correct 16 ms 26004 KB Output is correct
8 Correct 14 ms 26324 KB Output is correct
9 Correct 14 ms 25484 KB Output is correct
10 Correct 14 ms 26236 KB Output is correct
11 Correct 16 ms 26268 KB Output is correct
12 Correct 13 ms 25108 KB Output is correct
13 Correct 232 ms 210084 KB Output is correct
14 Correct 160 ms 143680 KB Output is correct
15 Correct 198 ms 161484 KB Output is correct
16 Correct 268 ms 177800 KB Output is correct
17 Correct 294 ms 203656 KB Output is correct
18 Correct 423 ms 262144 KB Output is correct
19 Correct 224 ms 188752 KB Output is correct
20 Correct 189 ms 143088 KB Output is correct
21 Correct 253 ms 203648 KB Output is correct
22 Correct 298 ms 236700 KB Output is correct
23 Correct 230 ms 200976 KB Output is correct
24 Correct 245 ms 184096 KB Output is correct
25 Correct 321 ms 191200 KB Output is correct
26 Correct 206 ms 146976 KB Output is correct
27 Correct 278 ms 184572 KB Output is correct
28 Correct 289 ms 183884 KB Output is correct
29 Correct 369 ms 230992 KB Output is correct
30 Correct 286 ms 199980 KB Output is correct
31 Correct 254 ms 187012 KB Output is correct
32 Correct 265 ms 212100 KB Output is correct
33 Correct 246 ms 173444 KB Output is correct
34 Correct 389 ms 232724 KB Output is correct
35 Correct 231 ms 151560 KB Output is correct
36 Correct 262 ms 160444 KB Output is correct
37 Correct 278 ms 174904 KB Output is correct
38 Correct 453 ms 261360 KB Output is correct
39 Correct 269 ms 225836 KB Output is correct
40 Runtime error 340 ms 262144 KB Execution killed with signal 9
41 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 14 ms 26400 KB Output is correct
3 Correct 15 ms 26708 KB Output is correct
4 Correct 13 ms 25180 KB Output is correct
5 Correct 13 ms 23956 KB Output is correct
6 Correct 13 ms 25748 KB Output is correct
7 Correct 16 ms 26004 KB Output is correct
8 Correct 14 ms 26324 KB Output is correct
9 Correct 14 ms 25484 KB Output is correct
10 Correct 14 ms 26236 KB Output is correct
11 Correct 16 ms 26268 KB Output is correct
12 Correct 13 ms 25108 KB Output is correct
13 Correct 232 ms 210084 KB Output is correct
14 Correct 160 ms 143680 KB Output is correct
15 Correct 198 ms 161484 KB Output is correct
16 Correct 268 ms 177800 KB Output is correct
17 Correct 294 ms 203656 KB Output is correct
18 Correct 423 ms 262144 KB Output is correct
19 Correct 224 ms 188752 KB Output is correct
20 Correct 189 ms 143088 KB Output is correct
21 Correct 253 ms 203648 KB Output is correct
22 Correct 298 ms 236700 KB Output is correct
23 Correct 230 ms 200976 KB Output is correct
24 Correct 245 ms 184096 KB Output is correct
25 Correct 321 ms 191200 KB Output is correct
26 Correct 206 ms 146976 KB Output is correct
27 Correct 278 ms 184572 KB Output is correct
28 Correct 289 ms 183884 KB Output is correct
29 Correct 369 ms 230992 KB Output is correct
30 Correct 286 ms 199980 KB Output is correct
31 Correct 254 ms 187012 KB Output is correct
32 Correct 333 ms 247076 KB Output is correct
33 Correct 208 ms 159588 KB Output is correct
34 Correct 192 ms 169548 KB Output is correct
35 Correct 327 ms 235648 KB Output is correct
36 Correct 264 ms 229256 KB Output is correct
37 Correct 279 ms 241568 KB Output is correct
38 Runtime error 342 ms 262144 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -