#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int Nmax=1000000;
int n, s, k, d[Nmax], v[Nmax], r[Nmax];
int st[Nmax+1], sol;
ll spd[Nmax], spv[Nmax], mx;
vector <int >ad[Nmax+1];
ll dist(int a, int b){
if (a==b)
return 0;
if (a==0)
return spd[b-1];
return spd[b-1]-spd[a-1];
}
ll vp(int a, int b){
if (a==0)
return spv[b];
return spv[b]-spv[a-1];
}
void dfs(int nod, int lev){
st[lev]=nod;
if (nod!=n){
int l;
if (lev<s)
l=n-1;
else l=st[lev-s]-1;
//cout<<nod<<' '<<l<<'\n';
if (vp(nod, l)>mx){
mx=vp(nod, l);
sol=nod;
}
}
for (int i=0; i<ad[nod].size(); i++)
dfs(ad[nod][i], lev+1);
}
int main()
{
cin>>n>>s>>k;
for (int i=0; i<n-1 ;i++)
cin>>d[i];
for (int i=0; i<n; i++)
cin>>v[i];
spd[0]=d[0];
for (int i=1; i<n-1; i++)
spd[i]=spd[i-1]+d[i];
spv[0]=v[0];
for (int i=1; i<n; i++)
spv[i]=spv[i-1]+v[i];
///cautam cel mai din dreapta modul din intervalul k
int p1=0;
for (int i=0; i<n; i++)
while (dist(p1, i)>k)
r[p1++]=i-1;
for (int i=p1; i<n; i++)
r[i]=n-1;
///cream arborele
for (int i=0; i<n; i++)
ad[r[r[i]]+1].push_back(i);
dfs(n, 0);
cout<<s<<'\n';
for (int i=0; i<s; i++){
//cout<<sol<<' ';
if (sol==n)
cout<<n<<' ';
else{
cout<<r[sol]+1<<' ';
sol=r[r[sol]]+1;
}
}
return 0;
}
Compilation message
SolarStorm.cpp: In function 'void dfs(int, int)':
SolarStorm.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i=0; i<ad[nod].size(); i++)
| ~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23796 KB |
Output is correct |
2 |
Correct |
14 ms |
24796 KB |
Output is correct |
3 |
Correct |
17 ms |
24956 KB |
Output is correct |
4 |
Correct |
13 ms |
24256 KB |
Output is correct |
5 |
Correct |
11 ms |
23836 KB |
Output is correct |
6 |
Correct |
14 ms |
24092 KB |
Output is correct |
7 |
Correct |
15 ms |
24156 KB |
Output is correct |
8 |
Correct |
15 ms |
24332 KB |
Output is correct |
9 |
Correct |
14 ms |
24116 KB |
Output is correct |
10 |
Correct |
18 ms |
24404 KB |
Output is correct |
11 |
Correct |
16 ms |
24316 KB |
Output is correct |
12 |
Correct |
13 ms |
24276 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
44844 KB |
Output is correct |
2 |
Correct |
236 ms |
48528 KB |
Output is correct |
3 |
Correct |
229 ms |
59176 KB |
Output is correct |
4 |
Correct |
267 ms |
66680 KB |
Output is correct |
5 |
Correct |
364 ms |
74224 KB |
Output is correct |
6 |
Correct |
419 ms |
91272 KB |
Output is correct |
7 |
Correct |
286 ms |
79196 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23796 KB |
Output is correct |
2 |
Correct |
14 ms |
24796 KB |
Output is correct |
3 |
Correct |
17 ms |
24956 KB |
Output is correct |
4 |
Correct |
13 ms |
24256 KB |
Output is correct |
5 |
Correct |
11 ms |
23836 KB |
Output is correct |
6 |
Correct |
14 ms |
24092 KB |
Output is correct |
7 |
Correct |
15 ms |
24156 KB |
Output is correct |
8 |
Correct |
15 ms |
24332 KB |
Output is correct |
9 |
Correct |
14 ms |
24116 KB |
Output is correct |
10 |
Correct |
18 ms |
24404 KB |
Output is correct |
11 |
Correct |
16 ms |
24316 KB |
Output is correct |
12 |
Correct |
13 ms |
24276 KB |
Output is correct |
13 |
Correct |
40 ms |
44844 KB |
Output is correct |
14 |
Correct |
236 ms |
48528 KB |
Output is correct |
15 |
Correct |
229 ms |
59176 KB |
Output is correct |
16 |
Correct |
267 ms |
66680 KB |
Output is correct |
17 |
Correct |
364 ms |
74224 KB |
Output is correct |
18 |
Correct |
419 ms |
91272 KB |
Output is correct |
19 |
Correct |
286 ms |
79196 KB |
Output is correct |
20 |
Incorrect |
31 ms |
38656 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
385 ms |
122336 KB |
Output is correct |
2 |
Correct |
228 ms |
83484 KB |
Output is correct |
3 |
Correct |
242 ms |
88152 KB |
Output is correct |
4 |
Correct |
344 ms |
116888 KB |
Output is correct |
5 |
Correct |
325 ms |
114040 KB |
Output is correct |
6 |
Correct |
359 ms |
119360 KB |
Output is correct |
7 |
Correct |
454 ms |
145724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23796 KB |
Output is correct |
2 |
Correct |
14 ms |
24796 KB |
Output is correct |
3 |
Correct |
17 ms |
24956 KB |
Output is correct |
4 |
Correct |
13 ms |
24256 KB |
Output is correct |
5 |
Correct |
11 ms |
23836 KB |
Output is correct |
6 |
Correct |
14 ms |
24092 KB |
Output is correct |
7 |
Correct |
15 ms |
24156 KB |
Output is correct |
8 |
Correct |
15 ms |
24332 KB |
Output is correct |
9 |
Correct |
14 ms |
24116 KB |
Output is correct |
10 |
Correct |
18 ms |
24404 KB |
Output is correct |
11 |
Correct |
16 ms |
24316 KB |
Output is correct |
12 |
Correct |
13 ms |
24276 KB |
Output is correct |
13 |
Incorrect |
11 ms |
24168 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23796 KB |
Output is correct |
2 |
Correct |
14 ms |
24796 KB |
Output is correct |
3 |
Correct |
17 ms |
24956 KB |
Output is correct |
4 |
Correct |
13 ms |
24256 KB |
Output is correct |
5 |
Correct |
11 ms |
23836 KB |
Output is correct |
6 |
Correct |
14 ms |
24092 KB |
Output is correct |
7 |
Correct |
15 ms |
24156 KB |
Output is correct |
8 |
Correct |
15 ms |
24332 KB |
Output is correct |
9 |
Correct |
14 ms |
24116 KB |
Output is correct |
10 |
Correct |
18 ms |
24404 KB |
Output is correct |
11 |
Correct |
16 ms |
24316 KB |
Output is correct |
12 |
Correct |
13 ms |
24276 KB |
Output is correct |
13 |
Correct |
40 ms |
44844 KB |
Output is correct |
14 |
Correct |
236 ms |
48528 KB |
Output is correct |
15 |
Correct |
229 ms |
59176 KB |
Output is correct |
16 |
Correct |
267 ms |
66680 KB |
Output is correct |
17 |
Correct |
364 ms |
74224 KB |
Output is correct |
18 |
Correct |
419 ms |
91272 KB |
Output is correct |
19 |
Correct |
286 ms |
79196 KB |
Output is correct |
20 |
Incorrect |
31 ms |
38656 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23796 KB |
Output is correct |
2 |
Correct |
14 ms |
24796 KB |
Output is correct |
3 |
Correct |
17 ms |
24956 KB |
Output is correct |
4 |
Correct |
13 ms |
24256 KB |
Output is correct |
5 |
Correct |
11 ms |
23836 KB |
Output is correct |
6 |
Correct |
14 ms |
24092 KB |
Output is correct |
7 |
Correct |
15 ms |
24156 KB |
Output is correct |
8 |
Correct |
15 ms |
24332 KB |
Output is correct |
9 |
Correct |
14 ms |
24116 KB |
Output is correct |
10 |
Correct |
18 ms |
24404 KB |
Output is correct |
11 |
Correct |
16 ms |
24316 KB |
Output is correct |
12 |
Correct |
13 ms |
24276 KB |
Output is correct |
13 |
Correct |
40 ms |
44844 KB |
Output is correct |
14 |
Correct |
236 ms |
48528 KB |
Output is correct |
15 |
Correct |
229 ms |
59176 KB |
Output is correct |
16 |
Correct |
267 ms |
66680 KB |
Output is correct |
17 |
Correct |
364 ms |
74224 KB |
Output is correct |
18 |
Correct |
419 ms |
91272 KB |
Output is correct |
19 |
Correct |
286 ms |
79196 KB |
Output is correct |
20 |
Incorrect |
31 ms |
38656 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |