oj.uz

Submission #224905

# Submission time Handle Problem Language Result Execution time Memory
224905 2020-04-19T05:03:16 Z nabilervatra Solar Storm (NOI20_solarstorm) C++14
52 / 100
 1113 ms 219844 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
long long n,m,k,psum[1000005],pref[1000005],x,p1,tab[1000005][25],cnt,tmp,now,ri,ans,p2,jwb[1000005];
bool sub4;
vector<long long> ret;
int main(){
    cin>>n>>m>>k;
    if(k==1)sub4=1;
    for(long long i =2;i<=n;i++){
        cin>>x;
        if(x<=1)sub4=0;
        pref[i]=pref[i-1]+x;
    }
    for(long long i =1;i<=n;i++){
        cin>>x;
        
        psum[i]=psum[i-1]+x;
    }
    if (sub4) {
        // cout<<'.';
        for(int i =1;i+m-1<=n;i++){
            if(psum[i+m-1]-psum[i-1]>ans)ans=psum[i+m-1]-psum[i-1];
        }
        for(int i=1;i+m-1<=n;i++){
            if(psum[i+m-1]-psum[i-1]==ans){
                cout<<m<<endl;
                for(int j =i;j<=i+m-2;j++){
                    cout<<j<<' ';
                }
                cout<<i+m-1<<endl;
                return 0;
            }
        }
    }
    p1=1;
    p2=1;
    for(long long i =1;i<=n;i++){
        p1=max(p1,(long long )i);
        
        while(pref[p1+1]-pref[i]<=k&&p1<n){
            p1++;
        }
        p2=max(p2,p1);
        while(pref[p2+1]-pref[p1]<=k&&p2<n){
            p2++;
        }
        tab[i][0]=p2;
    }
    for(long long j =1;j<=log2(m);j++){
        for(long long i =1;i<=n;i++){
            if(tab[i][j-1]==n)tab[i][j]=n;
            tab[i][j] = tab[tab[i][j-1]+1][j-1];
        }
    }
    for(long long i=1;i<=n;i++){
        tmp= log2(m);
        cnt=m;
        now=i;
        ri=i;
        while(cnt>0&&now<=n){
            if((1<<tmp)>cnt){
                tmp--;
                continue;
            }
            ri = tab[now][tmp];
            now=ri+1;
            cnt-=(1<<tmp);
            tmp--;
        }
        jwb[i]= psum[ri]-psum[i-1];
        ans = max(ans,jwb[i]);
    }
    for(long long i=1;i<=n;i++){
        if(jwb[i]==ans){
            cnt=m;
            p1=i;
            p2=i;
            while(cnt>0){ 
                if(p1==n){
                    if(ret.empty()||ret.back()!=n)ret.pb(n);
                    break;
                }
                p2=p1;
                while(pref[p2+1]-pref[p1]<=k&&p2<n)p2++;
                ret.pb(p2);
                p1=p2;
                while(pref[p1+1]-pref[p2]<=k&&p1<n)p1++;
                if(p1<n)p1++;
               
                cnt--;
            }
            break;
        }
    }
    cout<<ret.size()<<endl;
    for(long long i =0;i<ret.size();i++){
        cout<<ret[i];
        if(i<ret.size()-1)cout<<' ';
    }
    cout<<endl;
}

Compilation message

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:97:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i =0;i<ret.size();i++){
                        ~^~~~~~~~~~~
SolarStorm.cpp:99:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i<ret.size()-1)cout<<' ';
            ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 12 ms 2432 KB Output is correct
3 Correct 13 ms 2560 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 2176 KB Output is correct
7 Correct 12 ms 2304 KB Output is correct
8 Correct 13 ms 2688 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 188784 KB Output is correct
2 Correct 434 ms 120952 KB Output is correct
3 Correct 455 ms 129500 KB Output is correct
4 Correct 488 ms 141176 KB Output is correct
5 Correct 569 ms 165112 KB Output is correct
6 Correct 763 ms 219844 KB Output is correct
7 Correct 511 ms 145528 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 12 ms 2432 KB Output is correct
3 Correct 13 ms 2560 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 2176 KB Output is correct
7 Correct 12 ms 2304 KB Output is correct
8 Correct 13 ms 2688 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 652 ms 188784 KB Output is correct
14 Correct 434 ms 120952 KB Output is correct
15 Correct 455 ms 129500 KB Output is correct
16 Correct 488 ms 141176 KB Output is correct
17 Correct 569 ms 165112 KB Output is correct
18 Correct 763 ms 219844 KB Output is correct
19 Correct 511 ms 145528 KB Output is correct
20 Correct 558 ms 120628 KB Output is correct
21 Correct 684 ms 147704 KB Output is correct
22 Correct 783 ms 175096 KB Output is correct
23 Correct 718 ms 180316 KB Output is correct
24 Correct 743 ms 162936 KB Output is correct
25 Correct 735 ms 162936 KB Output is correct
26 Correct 561 ms 121720 KB Output is correct
27 Correct 714 ms 156024 KB Output is correct
28 Correct 705 ms 154360 KB Output is correct
29 Correct 914 ms 200224 KB Output is correct
30 Correct 744 ms 164088 KB Output is correct
31 Correct 649 ms 143968 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 591 ms 18296 KB Output is correct
2 Correct 338 ms 9456 KB Output is correct
3 Correct 355 ms 9848 KB Output is correct
4 Correct 517 ms 13944 KB Output is correct
5 Correct 493 ms 13396 KB Output is correct
6 Correct 532 ms 14200 KB Output is correct
7 Correct 694 ms 20860 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 12 ms 2432 KB Output is correct
3 Correct 13 ms 2560 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 2176 KB Output is correct
7 Correct 12 ms 2304 KB Output is correct
8 Correct 13 ms 2688 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 15 ms 2688 KB Output is correct
14 Incorrect 13 ms 2176 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 12 ms 2432 KB Output is correct
3 Correct 13 ms 2560 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 2176 KB Output is correct
7 Correct 12 ms 2304 KB Output is correct
8 Correct 13 ms 2688 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 652 ms 188784 KB Output is correct
14 Correct 434 ms 120952 KB Output is correct
15 Correct 455 ms 129500 KB Output is correct
16 Correct 488 ms 141176 KB Output is correct
17 Correct 569 ms 165112 KB Output is correct
18 Correct 763 ms 219844 KB Output is correct
19 Correct 511 ms 145528 KB Output is correct
20 Correct 558 ms 120628 KB Output is correct
21 Correct 684 ms 147704 KB Output is correct
22 Correct 783 ms 175096 KB Output is correct
23 Correct 718 ms 180316 KB Output is correct
24 Correct 743 ms 162936 KB Output is correct
25 Correct 735 ms 162936 KB Output is correct
26 Correct 561 ms 121720 KB Output is correct
27 Correct 714 ms 156024 KB Output is correct
28 Correct 705 ms 154360 KB Output is correct
29 Correct 914 ms 200224 KB Output is correct
30 Correct 744 ms 164088 KB Output is correct
31 Correct 649 ms 143968 KB Output is correct
32 Correct 946 ms 192376 KB Output is correct
33 Correct 764 ms 147576 KB Output is correct
34 Correct 1040 ms 202616 KB Output is correct
35 Correct 615 ms 121976 KB Output is correct
36 Correct 665 ms 130552 KB Output is correct
37 Correct 729 ms 143864 KB Output is correct
38 Correct 1113 ms 218092 KB Output is correct
39 Correct 819 ms 163704 KB Output is correct
40 Correct 1102 ms 219768 KB Output is correct

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 12 ms 2432 KB Output is correct
3 Correct 13 ms 2560 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 2176 KB Output is correct
7 Correct 12 ms 2304 KB Output is correct
8 Correct 13 ms 2688 KB Output is correct
9 Correct 10 ms 1792 KB Output is correct
10 Correct 13 ms 2560 KB Output is correct
11 Correct 14 ms 2560 KB Output is correct
12 Correct 8 ms 1280 KB Output is correct
13 Correct 652 ms 188784 KB Output is correct
14 Correct 434 ms 120952 KB Output is correct
15 Correct 455 ms 129500 KB Output is correct
16 Correct 488 ms 141176 KB Output is correct
17 Correct 569 ms 165112 KB Output is correct
18 Correct 763 ms 219844 KB Output is correct
19 Correct 511 ms 145528 KB Output is correct
20 Correct 558 ms 120628 KB Output is correct
21 Correct 684 ms 147704 KB Output is correct
22 Correct 783 ms 175096 KB Output is correct
23 Correct 718 ms 180316 KB Output is correct
24 Correct 743 ms 162936 KB Output is correct
25 Correct 735 ms 162936 KB Output is correct
26 Correct 561 ms 121720 KB Output is correct
27 Correct 714 ms 156024 KB Output is correct
28 Correct 705 ms 154360 KB Output is correct
29 Correct 914 ms 200224 KB Output is correct
30 Correct 744 ms 164088 KB Output is correct
31 Correct 649 ms 143968 KB Output is correct
32 Correct 591 ms 18296 KB Output is correct
33 Correct 338 ms 9456 KB Output is correct
34 Correct 355 ms 9848 KB Output is correct
35 Correct 517 ms 13944 KB Output is correct
36 Correct 493 ms 13396 KB Output is correct
37 Correct 532 ms 14200 KB Output is correct
38 Correct 694 ms 20860 KB Output is correct
39 Correct 15 ms 2688 KB Output is correct
40 Incorrect 13 ms 2176 KB Output isn't correct
41 Halted 0 ms 0 KB -