Submission #677362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
677362	2023-01-03T05:42:57 Z	penguin133	Solar Storm (NOI20_solarstorm)	C++17	46 / 100	2000 ms	31948 KB

SolarStorm

#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];

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];
	vector<int> fin;
	int mx =0 ;
	for(int i=1;i<=n;i++){
		int bt = i, rem = s;
		vector<int> v;
		while(rem && bt){
			int lo = 1, hi = bt, ans = hi;
			while(lo <= hi){
				int mid = (lo + hi) >> 1;
				if(P[bt] - 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;
			}
			bt = ans2 - 1;
			//if(i == 5)cout << ans2 << " ";
			rem--;
			v.push_back(ans);
			if(!bt || !rem){
				if(X[i] - X[ans2-1] > mx)mx = X[i] - X[ans2-1], fin = v;
			}
		}
	}
	//cout << mx << '\n';
	cout << (int)fin.size() << '\n';
	for(auto i : fin)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:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main(){
      | ^~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	724 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	3 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	3 ms	724 KB	Output is correct
11	Correct	3 ms	760 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	154 ms	27712 KB	Output is correct
2	Correct	107 ms	17688 KB	Output is correct
3	Correct	133 ms	19120 KB	Output is correct
4	Correct	121 ms	20804 KB	Output is correct
5	Correct	153 ms	24360 KB	Output is correct
6	Correct	181 ms	31948 KB	Output is correct
7	Correct	132 ms	21608 KB	Output is correct

Subtask #3

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	724 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	3 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	3 ms	724 KB	Output is correct
11	Correct	3 ms	760 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	154 ms	27712 KB	Output is correct
14	Correct	107 ms	17688 KB	Output is correct
15	Correct	133 ms	19120 KB	Output is correct
16	Correct	121 ms	20804 KB	Output is correct
17	Correct	153 ms	24360 KB	Output is correct
18	Correct	181 ms	31948 KB	Output is correct
19	Correct	132 ms	21608 KB	Output is correct
20	Correct	114 ms	17912 KB	Output is correct
21	Correct	163 ms	21788 KB	Output is correct
22	Correct	171 ms	25648 KB	Output is correct
23	Correct	152 ms	26400 KB	Output is correct
24	Correct	150 ms	23852 KB	Output is correct
25	Correct	173 ms	23960 KB	Output is correct
26	Correct	128 ms	17996 KB	Output is correct
27	Correct	169 ms	22892 KB	Output is correct
28	Correct	161 ms	22588 KB	Output is correct
29	Correct	226 ms	29252 KB	Output is correct
30	Correct	165 ms	24012 KB	Output is correct
31	Correct	143 ms	21228 KB	Output is correct

Subtask #4

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2039 ms	30616 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	724 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	3 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	3 ms	724 KB	Output is correct
11	Correct	3 ms	760 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	3 ms	724 KB	Output is correct
14	Correct	12 ms	596 KB	Output is correct
15	Correct	32 ms	728 KB	Output is correct
16	Correct	7 ms	596 KB	Output is correct
17	Correct	12 ms	700 KB	Output is correct
18	Correct	8 ms	724 KB	Output is correct
19	Correct	15 ms	600 KB	Output is correct
20	Correct	18 ms	588 KB	Output is correct
21	Correct	1437 ms	1384 KB	Output is correct
22	Correct	229 ms	852 KB	Output is correct
23	Correct	14 ms	852 KB	Output is correct
24	Correct	170 ms	820 KB	Output is correct
25	Correct	578 ms	948 KB	Output is correct
26	Correct	538 ms	904 KB	Output is correct
27	Correct	236 ms	768 KB	Output is correct
28	Correct	274 ms	788 KB	Output is correct
29	Correct	521 ms	844 KB	Output is correct
30	Correct	2 ms	724 KB	Output is correct

Subtask #6

0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	724 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	3 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	3 ms	724 KB	Output is correct
11	Correct	3 ms	760 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	154 ms	27712 KB	Output is correct
14	Correct	107 ms	17688 KB	Output is correct
15	Correct	133 ms	19120 KB	Output is correct
16	Correct	121 ms	20804 KB	Output is correct
17	Correct	153 ms	24360 KB	Output is correct
18	Correct	181 ms	31948 KB	Output is correct
19	Correct	132 ms	21608 KB	Output is correct
20	Correct	114 ms	17912 KB	Output is correct
21	Correct	163 ms	21788 KB	Output is correct
22	Correct	171 ms	25648 KB	Output is correct
23	Correct	152 ms	26400 KB	Output is correct
24	Correct	150 ms	23852 KB	Output is correct
25	Correct	173 ms	23960 KB	Output is correct
26	Correct	128 ms	17996 KB	Output is correct
27	Correct	169 ms	22892 KB	Output is correct
28	Correct	161 ms	22588 KB	Output is correct
29	Correct	226 ms	29252 KB	Output is correct
30	Correct	165 ms	24012 KB	Output is correct
31	Correct	143 ms	21228 KB	Output is correct
32	Correct	209 ms	29908 KB	Output is correct
33	Correct	200 ms	23500 KB	Output is correct
34	Execution timed out	2008 ms	31304 KB	Time limit exceeded
35	Halted	0 ms	0 KB	-

Subtask #7

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	724 KB	Output is correct
3	Correct	3 ms	724 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	596 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct
8	Correct	3 ms	724 KB	Output is correct
9	Correct	2 ms	596 KB	Output is correct
10	Correct	3 ms	724 KB	Output is correct
11	Correct	3 ms	760 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	154 ms	27712 KB	Output is correct
14	Correct	107 ms	17688 KB	Output is correct
15	Correct	133 ms	19120 KB	Output is correct
16	Correct	121 ms	20804 KB	Output is correct
17	Correct	153 ms	24360 KB	Output is correct
18	Correct	181 ms	31948 KB	Output is correct
19	Correct	132 ms	21608 KB	Output is correct
20	Correct	114 ms	17912 KB	Output is correct
21	Correct	163 ms	21788 KB	Output is correct
22	Correct	171 ms	25648 KB	Output is correct
23	Correct	152 ms	26400 KB	Output is correct
24	Correct	150 ms	23852 KB	Output is correct
25	Correct	173 ms	23960 KB	Output is correct
26	Correct	128 ms	17996 KB	Output is correct
27	Correct	169 ms	22892 KB	Output is correct
28	Correct	161 ms	22588 KB	Output is correct
29	Correct	226 ms	29252 KB	Output is correct
30	Correct	165 ms	24012 KB	Output is correct
31	Correct	143 ms	21228 KB	Output is correct
32	Execution timed out	2039 ms	30616 KB	Time limit exceeded
33	Halted	0 ms	0 KB	-