#include <iostream>
#include <vector>
#define vi vector<int>
#define fst first
#define snd second
#define pub push_back
#define ll long long
using namespace std;
const int MX = 1000001, LG = 20;
int s, n;
ll k, dst[MX] = {}, vpf[MX] = {}, sps[MX][LG] = {}, mx, rs, i1, i2, dst1, dst2;
vector<int> ans;
int main()
{
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> s >> k;
for (int i = 1; i < n; i++) {cin >> dst[i];}
for (int i = 1; i <= n; i++) {cin >> vpf[i]; vpf[i] += vpf[i - 1];}
//i1 = i2 = 1;
for (int i = 0; i < n; i++)
{
if (i2 < i) {dst2 = dst1 = 0; i2 = i1 = i;}
else if (i1 < i) {dst1 = 0; dst2 -= dst[i]; i1 = i;}
else {dst1 -= dst[i];}
for (; i1 < n - 1 && dst1 + dst[i1 + 1] <= k; i1++)
{
dst1 += dst[i1 + 1];
if (i1 + 1 <= i2) {dst2 -= dst[i1 + 1];}
else {i2++;}
}
for (; i2 < n - 1 && dst2 + dst[i2 + 1] <= k; i2++)
{
dst2 += dst[i2 + 1];
}
sps[i][0] = i2;
//cout << i1 << " " << i2 << "\n";
}
for (int i = 1; (1 << i) <= s; i++)
{
for (int j = 0; j < n; j++)
{
if (sps[j][i - 1] == n - 1) {sps[j][i] = n - 1;}
else {sps[j][i] = sps[sps[j][i - 1] + 1][i - 1];}
}
}
//cout << "----\n";
for (int i = 0; i < n; i++)
{
int cr = i - 1;
for (int j = 0; (1 << j) <= s; j++)
{
if ((1 << j) & s)
{
if (cr < n - 1) {cr = sps[cr + 1][j];}
}
}
//cout << i << " " << cr << "\n";
if (vpf[cr + 1] - vpf[i] > mx)
{
mx = vpf[cr + 1] - vpf[i];
rs = i;
}
}
//cout << mx << "\n";
i1 = rs, i2 = rs, dst1 = 0, dst2 = 0;
while (ans.size() < s && rs < n)
{
for (; i1 < n - 1 && dst1 + dst[i1 + 1] <= k; i1++)
{
dst1 += dst[i1 + 1];
if (i1 + 1 <= i2) {dst2 -= dst[i1 + 1];}
else {i2++;}
}
for (; i2 < n - 1 && dst2 + dst[i2 + 1] <= k; i2++)
{
dst2 += dst[i2 + 1];
}
ans.pub(i1 + 1);
rs = i2 + 1;
i1 = rs;
i2 = rs;
dst1 = 0;
dst2 = 0;
}
cout << ans.size() << "\n";
for (int i = 0; i < ans.size(); i++)
{
cout << ans[i];
if (i < ans.size() - 1) {cout << " ";}
}
cout << "\n";
return 0;
}
Compilation message
SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ans.size() < s && rs < n)
~~~~~~~~~~~^~~
SolarStorm.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < ans.size(); i++)
~~^~~~~~~~~~~~
SolarStorm.cpp:90:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < ans.size() - 1) {cout << " ";}
~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
7 ms |
2176 KB |
Output is correct |
4 |
Correct |
6 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1792 KB |
Output is correct |
7 |
Correct |
7 ms |
1920 KB |
Output is correct |
8 |
Correct |
7 ms |
2176 KB |
Output is correct |
9 |
Correct |
6 ms |
1536 KB |
Output is correct |
10 |
Correct |
7 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
2176 KB |
Output is correct |
12 |
Correct |
6 ms |
1152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
223 ms |
155000 KB |
Output is correct |
2 |
Correct |
139 ms |
98936 KB |
Output is correct |
3 |
Correct |
144 ms |
105976 KB |
Output is correct |
4 |
Correct |
158 ms |
115704 KB |
Output is correct |
5 |
Correct |
186 ms |
135580 KB |
Output is correct |
6 |
Correct |
248 ms |
178936 KB |
Output is correct |
7 |
Correct |
172 ms |
119288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
7 ms |
2176 KB |
Output is correct |
4 |
Correct |
6 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1792 KB |
Output is correct |
7 |
Correct |
7 ms |
1920 KB |
Output is correct |
8 |
Correct |
7 ms |
2176 KB |
Output is correct |
9 |
Correct |
6 ms |
1536 KB |
Output is correct |
10 |
Correct |
7 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
2176 KB |
Output is correct |
12 |
Correct |
6 ms |
1152 KB |
Output is correct |
13 |
Correct |
223 ms |
155000 KB |
Output is correct |
14 |
Correct |
139 ms |
98936 KB |
Output is correct |
15 |
Correct |
144 ms |
105976 KB |
Output is correct |
16 |
Correct |
158 ms |
115704 KB |
Output is correct |
17 |
Correct |
186 ms |
135580 KB |
Output is correct |
18 |
Correct |
248 ms |
178936 KB |
Output is correct |
19 |
Correct |
172 ms |
119288 KB |
Output is correct |
20 |
Correct |
165 ms |
101112 KB |
Output is correct |
21 |
Correct |
205 ms |
121952 KB |
Output is correct |
22 |
Correct |
249 ms |
142968 KB |
Output is correct |
23 |
Correct |
238 ms |
147940 KB |
Output is correct |
24 |
Correct |
227 ms |
133496 KB |
Output is correct |
25 |
Correct |
235 ms |
133592 KB |
Output is correct |
26 |
Correct |
169 ms |
101852 KB |
Output is correct |
27 |
Correct |
225 ms |
128248 KB |
Output is correct |
28 |
Correct |
224 ms |
126968 KB |
Output is correct |
29 |
Correct |
293 ms |
161528 KB |
Output is correct |
30 |
Correct |
238 ms |
134520 KB |
Output is correct |
31 |
Correct |
196 ms |
119420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
505 ms |
151392 KB |
Output is correct |
2 |
Correct |
224 ms |
91896 KB |
Output is correct |
3 |
Correct |
201 ms |
98680 KB |
Output is correct |
4 |
Correct |
291 ms |
142840 KB |
Output is correct |
5 |
Correct |
247 ms |
138488 KB |
Output is correct |
6 |
Correct |
218 ms |
146424 KB |
Output is correct |
7 |
Correct |
666 ms |
184808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
7 ms |
2176 KB |
Output is correct |
4 |
Correct |
6 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1792 KB |
Output is correct |
7 |
Correct |
7 ms |
1920 KB |
Output is correct |
8 |
Correct |
7 ms |
2176 KB |
Output is correct |
9 |
Correct |
6 ms |
1536 KB |
Output is correct |
10 |
Correct |
7 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
2176 KB |
Output is correct |
12 |
Correct |
6 ms |
1152 KB |
Output is correct |
13 |
Correct |
8 ms |
2176 KB |
Output is correct |
14 |
Correct |
7 ms |
1792 KB |
Output is correct |
15 |
Correct |
7 ms |
1792 KB |
Output is correct |
16 |
Correct |
6 ms |
1408 KB |
Output is correct |
17 |
Correct |
7 ms |
1792 KB |
Output is correct |
18 |
Correct |
8 ms |
2176 KB |
Output is correct |
19 |
Correct |
7 ms |
1792 KB |
Output is correct |
20 |
Correct |
6 ms |
1536 KB |
Output is correct |
21 |
Correct |
9 ms |
2304 KB |
Output is correct |
22 |
Correct |
8 ms |
2176 KB |
Output is correct |
23 |
Correct |
8 ms |
2176 KB |
Output is correct |
24 |
Correct |
9 ms |
1920 KB |
Output is correct |
25 |
Correct |
8 ms |
2048 KB |
Output is correct |
26 |
Correct |
8 ms |
2048 KB |
Output is correct |
27 |
Correct |
7 ms |
1664 KB |
Output is correct |
28 |
Correct |
7 ms |
1792 KB |
Output is correct |
29 |
Correct |
7 ms |
1664 KB |
Output is correct |
30 |
Correct |
8 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
7 ms |
2176 KB |
Output is correct |
4 |
Correct |
6 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1792 KB |
Output is correct |
7 |
Correct |
7 ms |
1920 KB |
Output is correct |
8 |
Correct |
7 ms |
2176 KB |
Output is correct |
9 |
Correct |
6 ms |
1536 KB |
Output is correct |
10 |
Correct |
7 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
2176 KB |
Output is correct |
12 |
Correct |
6 ms |
1152 KB |
Output is correct |
13 |
Correct |
223 ms |
155000 KB |
Output is correct |
14 |
Correct |
139 ms |
98936 KB |
Output is correct |
15 |
Correct |
144 ms |
105976 KB |
Output is correct |
16 |
Correct |
158 ms |
115704 KB |
Output is correct |
17 |
Correct |
186 ms |
135580 KB |
Output is correct |
18 |
Correct |
248 ms |
178936 KB |
Output is correct |
19 |
Correct |
172 ms |
119288 KB |
Output is correct |
20 |
Correct |
165 ms |
101112 KB |
Output is correct |
21 |
Correct |
205 ms |
121952 KB |
Output is correct |
22 |
Correct |
249 ms |
142968 KB |
Output is correct |
23 |
Correct |
238 ms |
147940 KB |
Output is correct |
24 |
Correct |
227 ms |
133496 KB |
Output is correct |
25 |
Correct |
235 ms |
133592 KB |
Output is correct |
26 |
Correct |
169 ms |
101852 KB |
Output is correct |
27 |
Correct |
225 ms |
128248 KB |
Output is correct |
28 |
Correct |
224 ms |
126968 KB |
Output is correct |
29 |
Correct |
293 ms |
161528 KB |
Output is correct |
30 |
Correct |
238 ms |
134520 KB |
Output is correct |
31 |
Correct |
196 ms |
119420 KB |
Output is correct |
32 |
Correct |
297 ms |
155256 KB |
Output is correct |
33 |
Correct |
252 ms |
121464 KB |
Output is correct |
34 |
Correct |
376 ms |
162936 KB |
Output is correct |
35 |
Correct |
235 ms |
102392 KB |
Output is correct |
36 |
Correct |
232 ms |
108920 KB |
Output is correct |
37 |
Correct |
269 ms |
119048 KB |
Output is correct |
38 |
Correct |
358 ms |
175224 KB |
Output is correct |
39 |
Correct |
270 ms |
134264 KB |
Output is correct |
40 |
Correct |
365 ms |
176804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
7 ms |
2048 KB |
Output is correct |
3 |
Correct |
7 ms |
2176 KB |
Output is correct |
4 |
Correct |
6 ms |
1152 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
7 ms |
1792 KB |
Output is correct |
7 |
Correct |
7 ms |
1920 KB |
Output is correct |
8 |
Correct |
7 ms |
2176 KB |
Output is correct |
9 |
Correct |
6 ms |
1536 KB |
Output is correct |
10 |
Correct |
7 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
2176 KB |
Output is correct |
12 |
Correct |
6 ms |
1152 KB |
Output is correct |
13 |
Correct |
223 ms |
155000 KB |
Output is correct |
14 |
Correct |
139 ms |
98936 KB |
Output is correct |
15 |
Correct |
144 ms |
105976 KB |
Output is correct |
16 |
Correct |
158 ms |
115704 KB |
Output is correct |
17 |
Correct |
186 ms |
135580 KB |
Output is correct |
18 |
Correct |
248 ms |
178936 KB |
Output is correct |
19 |
Correct |
172 ms |
119288 KB |
Output is correct |
20 |
Correct |
165 ms |
101112 KB |
Output is correct |
21 |
Correct |
205 ms |
121952 KB |
Output is correct |
22 |
Correct |
249 ms |
142968 KB |
Output is correct |
23 |
Correct |
238 ms |
147940 KB |
Output is correct |
24 |
Correct |
227 ms |
133496 KB |
Output is correct |
25 |
Correct |
235 ms |
133592 KB |
Output is correct |
26 |
Correct |
169 ms |
101852 KB |
Output is correct |
27 |
Correct |
225 ms |
128248 KB |
Output is correct |
28 |
Correct |
224 ms |
126968 KB |
Output is correct |
29 |
Correct |
293 ms |
161528 KB |
Output is correct |
30 |
Correct |
238 ms |
134520 KB |
Output is correct |
31 |
Correct |
196 ms |
119420 KB |
Output is correct |
32 |
Correct |
505 ms |
151392 KB |
Output is correct |
33 |
Correct |
224 ms |
91896 KB |
Output is correct |
34 |
Correct |
201 ms |
98680 KB |
Output is correct |
35 |
Correct |
291 ms |
142840 KB |
Output is correct |
36 |
Correct |
247 ms |
138488 KB |
Output is correct |
37 |
Correct |
218 ms |
146424 KB |
Output is correct |
38 |
Correct |
666 ms |
184808 KB |
Output is correct |
39 |
Correct |
8 ms |
2176 KB |
Output is correct |
40 |
Correct |
7 ms |
1792 KB |
Output is correct |
41 |
Correct |
7 ms |
1792 KB |
Output is correct |
42 |
Correct |
6 ms |
1408 KB |
Output is correct |
43 |
Correct |
7 ms |
1792 KB |
Output is correct |
44 |
Correct |
8 ms |
2176 KB |
Output is correct |
45 |
Correct |
7 ms |
1792 KB |
Output is correct |
46 |
Correct |
6 ms |
1536 KB |
Output is correct |
47 |
Correct |
9 ms |
2304 KB |
Output is correct |
48 |
Correct |
8 ms |
2176 KB |
Output is correct |
49 |
Correct |
8 ms |
2176 KB |
Output is correct |
50 |
Correct |
9 ms |
1920 KB |
Output is correct |
51 |
Correct |
8 ms |
2048 KB |
Output is correct |
52 |
Correct |
8 ms |
2048 KB |
Output is correct |
53 |
Correct |
7 ms |
1664 KB |
Output is correct |
54 |
Correct |
7 ms |
1792 KB |
Output is correct |
55 |
Correct |
7 ms |
1664 KB |
Output is correct |
56 |
Correct |
8 ms |
2048 KB |
Output is correct |
57 |
Correct |
297 ms |
155256 KB |
Output is correct |
58 |
Correct |
252 ms |
121464 KB |
Output is correct |
59 |
Correct |
376 ms |
162936 KB |
Output is correct |
60 |
Correct |
235 ms |
102392 KB |
Output is correct |
61 |
Correct |
232 ms |
108920 KB |
Output is correct |
62 |
Correct |
269 ms |
119048 KB |
Output is correct |
63 |
Correct |
358 ms |
175224 KB |
Output is correct |
64 |
Correct |
270 ms |
134264 KB |
Output is correct |
65 |
Correct |
365 ms |
176804 KB |
Output is correct |
66 |
Correct |
300 ms |
109688 KB |
Output is correct |
67 |
Correct |
513 ms |
150892 KB |
Output is correct |
68 |
Correct |
355 ms |
106852 KB |
Output is correct |
69 |
Correct |
456 ms |
139244 KB |
Output is correct |
70 |
Correct |
231 ms |
112508 KB |
Output is correct |
71 |
Correct |
450 ms |
174968 KB |
Output is correct |
72 |
Correct |
286 ms |
113528 KB |
Output is correct |
73 |
Correct |
349 ms |
145688 KB |
Output is correct |
74 |
Correct |
238 ms |
93588 KB |
Output is correct |
75 |
Correct |
380 ms |
148984 KB |
Output is correct |
76 |
Correct |
250 ms |
106616 KB |
Output is correct |
77 |
Correct |
423 ms |
140024 KB |
Output is correct |
78 |
Correct |
224 ms |
101880 KB |
Output is correct |
79 |
Correct |
322 ms |
129844 KB |
Output is correct |
80 |
Correct |
385 ms |
159688 KB |
Output is correct |
81 |
Correct |
192 ms |
108152 KB |
Output is correct |
82 |
Correct |
272 ms |
134476 KB |
Output is correct |
83 |
Correct |
188 ms |
91896 KB |
Output is correct |
84 |
Correct |
175 ms |
99324 KB |
Output is correct |
85 |
Correct |
205 ms |
93432 KB |
Output is correct |
86 |
Correct |
316 ms |
158840 KB |
Output is correct |
87 |
Correct |
198 ms |
93432 KB |
Output is correct |
88 |
Correct |
555 ms |
159532 KB |
Output is correct |
89 |
Correct |
257 ms |
130168 KB |
Output is correct |
90 |
Correct |
225 ms |
119032 KB |
Output is correct |
91 |
Correct |
699 ms |
186404 KB |
Output is correct |
92 |
Correct |
523 ms |
176476 KB |
Output is correct |
93 |
Correct |
713 ms |
181308 KB |
Output is correct |
94 |
Correct |
702 ms |
181232 KB |
Output is correct |
95 |
Correct |
511 ms |
156664 KB |
Output is correct |
96 |
Correct |
401 ms |
124280 KB |
Output is correct |
97 |
Correct |
594 ms |
167028 KB |
Output is correct |
98 |
Correct |
473 ms |
113136 KB |
Output is correct |
99 |
Correct |
437 ms |
126604 KB |
Output is correct |
100 |
Correct |
455 ms |
122976 KB |
Output is correct |