oj.uz

답안 #807702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807702 2023-08-04T22:03:14 Z AndiR Solar Storm (NOI20_solarstorm) C++14
100 / 100
 598 ms 169432 KB 
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
const ll Nmax=1000000;

ll n, s, k, d[Nmax], v[Nmax], r[Nmax];
ll st[Nmax+1], sol;
ll spd[Nmax], spv[Nmax], mx;

vector <ll >ad[Nmax+1];
ll dist(ll a, ll b){
    if (a==b)
        return 0;
    if (a==0)
        return spd[b-1];
    return spd[b-1]-spd[a-1];
}
ll vp(ll a, ll b){
    if (a==0)
        return spv[b];
    return spv[b]-spv[a-1];
}
void dfs(ll nod, ll lev){
    st[lev]=nod;
    if (nod!=n){
        ll 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 (ll i=0; i<ad[nod].size(); i++)
        dfs(ad[nod][i], lev+1);
}
int main()
{
    cin>>n>>s>>k;
    for (ll i=0; i<n-1 ;i++)
        cin>>d[i];
    for (ll i=0; i<n; i++)
        cin>>v[i];
    spd[0]=d[0];
    for (ll i=1; i<n-1; i++)
        spd[i]=spd[i-1]+d[i];
    spv[0]=v[0];
    for (ll i=1; i<n; i++)
        spv[i]=spv[i-1]+v[i];
    ///cautam cel mai din dreapta modul din intervalul k
    ll p1=0;
    for (ll i=0; i<n; i++)
        while (dist(p1, i)>k)
            r[p1++]=i-1;
    for (ll i=p1; i<n; i++)
        r[i]=n-1;
    ///cream arborele
    for (ll i=0; i<n; i++)
        ad[r[r[i]]+1].push_back(i);
    dfs(n, 0);
    cout<<s<<'\n';
    for (ll 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(ll, ll)':
SolarStorm.cpp:38:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (ll i=0; i<ad[nod].size(); i++)
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23828 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 16 ms 25008 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 11 ms 23760 KB Output is correct
6 Correct 15 ms 24248 KB Output is correct
7 Correct 15 ms 24328 KB Output is correct
8 Correct 15 ms 24324 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 15 ms 24404 KB Output is correct
11 Correct 16 ms 24404 KB Output is correct
12 Correct 13 ms 24336 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 309 ms 65592 KB Output is correct
2 Correct 209 ms 52372 KB Output is correct
3 Correct 222 ms 62068 KB Output is correct
4 Correct 285 ms 68692 KB Output is correct
5 Correct 327 ms 76472 KB Output is correct
6 Correct 402 ms 94284 KB Output is correct
7 Correct 282 ms 82092 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23828 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 16 ms 25008 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 11 ms 23760 KB Output is correct
6 Correct 15 ms 24248 KB Output is correct
7 Correct 15 ms 24328 KB Output is correct
8 Correct 15 ms 24324 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 15 ms 24404 KB Output is correct
11 Correct 16 ms 24404 KB Output is correct
12 Correct 13 ms 24336 KB Output is correct
13 Correct 309 ms 65592 KB Output is correct
14 Correct 209 ms 52372 KB Output is correct
15 Correct 222 ms 62068 KB Output is correct
16 Correct 285 ms 68692 KB Output is correct
17 Correct 327 ms 76472 KB Output is correct
18 Correct 402 ms 94284 KB Output is correct
19 Correct 282 ms 82092 KB Output is correct
20 Correct 260 ms 53408 KB Output is correct
21 Correct 357 ms 116220 KB Output is correct
22 Correct 411 ms 133588 KB Output is correct
23 Correct 327 ms 72692 KB Output is correct
24 Correct 365 ms 70848 KB Output is correct
25 Correct 398 ms 76224 KB Output is correct
26 Correct 300 ms 61784 KB Output is correct
27 Correct 355 ms 74180 KB Output is correct
28 Correct 371 ms 74288 KB Output is correct
29 Correct 523 ms 89660 KB Output is correct
30 Correct 391 ms 89316 KB Output is correct
31 Correct 346 ms 95852 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 127852 KB Output is correct
2 Correct 213 ms 87056 KB Output is correct
3 Correct 230 ms 91820 KB Output is correct
4 Correct 377 ms 122348 KB Output is correct
5 Correct 321 ms 119396 KB Output is correct
6 Correct 350 ms 125076 KB Output is correct
7 Correct 471 ms 152656 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23828 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 16 ms 25008 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 11 ms 23760 KB Output is correct
6 Correct 15 ms 24248 KB Output is correct
7 Correct 15 ms 24328 KB Output is correct
8 Correct 15 ms 24324 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 15 ms 24404 KB Output is correct
11 Correct 16 ms 24404 KB Output is correct
12 Correct 13 ms 24336 KB Output is correct
13 Correct 16 ms 24428 KB Output is correct
14 Correct 18 ms 24320 KB Output is correct
15 Correct 15 ms 24404 KB Output is correct
16 Correct 14 ms 24264 KB Output is correct
17 Correct 15 ms 24788 KB Output is correct
18 Correct 17 ms 25080 KB Output is correct
19 Correct 18 ms 24828 KB Output is correct
20 Correct 14 ms 24660 KB Output is correct
21 Correct 17 ms 25172 KB Output is correct
22 Correct 16 ms 25172 KB Output is correct
23 Correct 17 ms 24432 KB Output is correct
24 Correct 20 ms 24520 KB Output is correct
25 Correct 17 ms 24572 KB Output is correct
26 Correct 21 ms 24960 KB Output is correct
27 Correct 15 ms 24660 KB Output is correct
28 Correct 15 ms 24856 KB Output is correct
29 Correct 15 ms 24824 KB Output is correct
30 Correct 15 ms 24532 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23828 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 16 ms 25008 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 11 ms 23760 KB Output is correct
6 Correct 15 ms 24248 KB Output is correct
7 Correct 15 ms 24328 KB Output is correct
8 Correct 15 ms 24324 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 15 ms 24404 KB Output is correct
11 Correct 16 ms 24404 KB Output is correct
12 Correct 13 ms 24336 KB Output is correct
13 Correct 309 ms 65592 KB Output is correct
14 Correct 209 ms 52372 KB Output is correct
15 Correct 222 ms 62068 KB Output is correct
16 Correct 285 ms 68692 KB Output is correct
17 Correct 327 ms 76472 KB Output is correct
18 Correct 402 ms 94284 KB Output is correct
19 Correct 282 ms 82092 KB Output is correct
20 Correct 260 ms 53408 KB Output is correct
21 Correct 357 ms 116220 KB Output is correct
22 Correct 411 ms 133588 KB Output is correct
23 Correct 327 ms 72692 KB Output is correct
24 Correct 365 ms 70848 KB Output is correct
25 Correct 398 ms 76224 KB Output is correct
26 Correct 300 ms 61784 KB Output is correct
27 Correct 355 ms 74180 KB Output is correct
28 Correct 371 ms 74288 KB Output is correct
29 Correct 523 ms 89660 KB Output is correct
30 Correct 391 ms 89316 KB Output is correct
31 Correct 346 ms 95852 KB Output is correct
32 Correct 409 ms 77912 KB Output is correct
33 Correct 343 ms 70716 KB Output is correct
34 Correct 484 ms 90176 KB Output is correct
35 Correct 306 ms 63692 KB Output is correct
36 Correct 319 ms 66732 KB Output is correct
37 Correct 378 ms 72384 KB Output is correct
38 Correct 519 ms 118364 KB Output is correct
39 Correct 389 ms 125788 KB Output is correct
40 Correct 531 ms 162368 KB Output is correct

Subtask #7
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 23828 KB Output is correct
2 Correct 18 ms 24848 KB Output is correct
3 Correct 16 ms 25008 KB Output is correct
4 Correct 14 ms 24276 KB Output is correct
5 Correct 11 ms 23760 KB Output is correct
6 Correct 15 ms 24248 KB Output is correct
7 Correct 15 ms 24328 KB Output is correct
8 Correct 15 ms 24324 KB Output is correct
9 Correct 14 ms 24216 KB Output is correct
10 Correct 15 ms 24404 KB Output is correct
11 Correct 16 ms 24404 KB Output is correct
12 Correct 13 ms 24336 KB Output is correct
13 Correct 309 ms 65592 KB Output is correct
14 Correct 209 ms 52372 KB Output is correct
15 Correct 222 ms 62068 KB Output is correct
16 Correct 285 ms 68692 KB Output is correct
17 Correct 327 ms 76472 KB Output is correct
18 Correct 402 ms 94284 KB Output is correct
19 Correct 282 ms 82092 KB Output is correct
20 Correct 260 ms 53408 KB Output is correct
21 Correct 357 ms 116220 KB Output is correct
22 Correct 411 ms 133588 KB Output is correct
23 Correct 327 ms 72692 KB Output is correct
24 Correct 365 ms 70848 KB Output is correct
25 Correct 398 ms 76224 KB Output is correct
26 Correct 300 ms 61784 KB Output is correct
27 Correct 355 ms 74180 KB Output is correct
28 Correct 371 ms 74288 KB Output is correct
29 Correct 523 ms 89660 KB Output is correct
30 Correct 391 ms 89316 KB Output is correct
31 Correct 346 ms 95852 KB Output is correct
32 Correct 383 ms 127852 KB Output is correct
33 Correct 213 ms 87056 KB Output is correct
34 Correct 230 ms 91820 KB Output is correct
35 Correct 377 ms 122348 KB Output is correct
36 Correct 321 ms 119396 KB Output is correct
37 Correct 350 ms 125076 KB Output is correct
38 Correct 471 ms 152656 KB Output is correct
39 Correct 16 ms 24428 KB Output is correct
40 Correct 18 ms 24320 KB Output is correct
41 Correct 15 ms 24404 KB Output is correct
42 Correct 14 ms 24264 KB Output is correct
43 Correct 15 ms 24788 KB Output is correct
44 Correct 17 ms 25080 KB Output is correct
45 Correct 18 ms 24828 KB Output is correct
46 Correct 14 ms 24660 KB Output is correct
47 Correct 17 ms 25172 KB Output is correct
48 Correct 16 ms 25172 KB Output is correct
49 Correct 17 ms 24432 KB Output is correct
50 Correct 20 ms 24520 KB Output is correct
51 Correct 17 ms 24572 KB Output is correct
52 Correct 21 ms 24960 KB Output is correct
53 Correct 15 ms 24660 KB Output is correct
54 Correct 15 ms 24856 KB Output is correct
55 Correct 15 ms 24824 KB Output is correct
56 Correct 15 ms 24532 KB Output is correct
57 Correct 409 ms 77912 KB Output is correct
58 Correct 343 ms 70716 KB Output is correct
59 Correct 484 ms 90176 KB Output is correct
60 Correct 306 ms 63692 KB Output is correct
61 Correct 319 ms 66732 KB Output is correct
62 Correct 378 ms 72384 KB Output is correct
63 Correct 519 ms 118364 KB Output is correct
64 Correct 389 ms 125788 KB Output is correct
65 Correct 531 ms 162368 KB Output is correct
66 Correct 333 ms 63968 KB Output is correct
67 Correct 454 ms 140136 KB Output is correct
68 Correct 324 ms 103132 KB Output is correct
69 Correct 414 ms 131280 KB Output is correct
70 Correct 298 ms 64764 KB Output is correct
71 Correct 581 ms 95556 KB Output is correct
72 Correct 395 ms 69252 KB Output is correct
73 Correct 444 ms 84644 KB Output is correct
74 Correct 286 ms 78484 KB Output is correct
75 Correct 455 ms 137520 KB Output is correct
76 Correct 314 ms 104872 KB Output is correct
77 Correct 415 ms 80640 KB Output is correct
78 Correct 292 ms 101128 KB Output is correct
79 Correct 534 ms 124268 KB Output is correct
80 Correct 516 ms 149536 KB Output is correct
81 Correct 278 ms 63552 KB Output is correct
82 Correct 386 ms 76860 KB Output is correct
83 Correct 275 ms 60000 KB Output is correct
84 Correct 294 ms 63280 KB Output is correct
85 Correct 274 ms 60680 KB Output is correct
86 Correct 482 ms 91220 KB Output is correct
87 Correct 270 ms 74828 KB Output is correct
88 Correct 525 ms 93544 KB Output is correct
89 Correct 400 ms 124564 KB Output is correct
90 Correct 352 ms 115088 KB Output is correct
91 Correct 598 ms 169432 KB Output is correct
92 Correct 544 ms 162848 KB Output is correct
93 Correct 577 ms 166092 KB Output is correct
94 Correct 573 ms 166128 KB Output is correct
95 Correct 497 ms 90700 KB Output is correct
96 Correct 431 ms 79052 KB Output is correct
97 Correct 527 ms 100408 KB Output is correct
98 Correct 400 ms 82848 KB Output is correct
99 Correct 390 ms 119600 KB Output is correct
100 Correct 385 ms 117896 KB Output is correct