oj.uz

Submission #224903

# Submission time Handle Problem Language Result Execution time Memory
224903 2020-04-19T05:00:13 Z nabilervatra Solar Storm (NOI20_solarstorm) C++14
52 / 100
 1084 ms 194040 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][20],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 13 ms 2048 KB Output is correct
3 Correct 14 ms 2304 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 13 ms 2048 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 8 ms 1152 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 649 ms 156164 KB Output is correct
2 Correct 420 ms 100600 KB Output is correct
3 Correct 433 ms 107488 KB Output is correct
4 Correct 469 ms 117112 KB Output is correct
5 Correct 565 ms 136444 KB Output is correct
6 Correct 751 ms 181368 KB Output is correct
7 Correct 498 ms 120952 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 13 ms 2048 KB Output is correct
3 Correct 14 ms 2304 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 13 ms 2048 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 8 ms 1152 KB Output is correct
13 Correct 649 ms 156164 KB Output is correct
14 Correct 420 ms 100600 KB Output is correct
15 Correct 433 ms 107488 KB Output is correct
16 Correct 469 ms 117112 KB Output is correct
17 Correct 565 ms 136444 KB Output is correct
18 Correct 751 ms 181368 KB Output is correct
19 Correct 498 ms 120952 KB Output is correct
20 Correct 554 ms 99628 KB Output is correct
21 Correct 670 ms 121976 KB Output is correct
22 Correct 780 ms 144632 KB Output is correct
23 Correct 712 ms 149112 KB Output is correct
24 Correct 723 ms 134696 KB Output is correct
25 Correct 741 ms 134776 KB Output is correct
26 Correct 555 ms 101192 KB Output is correct
27 Correct 701 ms 129136 KB Output is correct
28 Correct 699 ms 127608 KB Output is correct
29 Correct 900 ms 165132 KB Output is correct
30 Correct 739 ms 135588 KB Output is correct
31 Correct 640 ms 119032 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 589 ms 19288 KB Output is correct
2 Correct 337 ms 9848 KB Output is correct
3 Correct 355 ms 10380 KB Output is correct
4 Correct 529 ms 14028 KB Output is correct
5 Correct 522 ms 13944 KB Output is correct
6 Correct 533 ms 14456 KB Output is correct
7 Correct 699 ms 20984 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 13 ms 2048 KB Output is correct
3 Correct 14 ms 2304 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 13 ms 2048 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 8 ms 1152 KB Output is correct
13 Correct 15 ms 2304 KB Output is correct
14 Incorrect 13 ms 1920 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 13 ms 2048 KB Output is correct
3 Correct 14 ms 2304 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 13 ms 2048 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 8 ms 1152 KB Output is correct
13 Correct 649 ms 156164 KB Output is correct
14 Correct 420 ms 100600 KB Output is correct
15 Correct 433 ms 107488 KB Output is correct
16 Correct 469 ms 117112 KB Output is correct
17 Correct 565 ms 136444 KB Output is correct
18 Correct 751 ms 181368 KB Output is correct
19 Correct 498 ms 120952 KB Output is correct
20 Correct 554 ms 99628 KB Output is correct
21 Correct 670 ms 121976 KB Output is correct
22 Correct 780 ms 144632 KB Output is correct
23 Correct 712 ms 149112 KB Output is correct
24 Correct 723 ms 134696 KB Output is correct
25 Correct 741 ms 134776 KB Output is correct
26 Correct 555 ms 101192 KB Output is correct
27 Correct 701 ms 129136 KB Output is correct
28 Correct 699 ms 127608 KB Output is correct
29 Correct 900 ms 165132 KB Output is correct
30 Correct 739 ms 135588 KB Output is correct
31 Correct 640 ms 119032 KB Output is correct
32 Correct 919 ms 158408 KB Output is correct
33 Correct 719 ms 121720 KB Output is correct
34 Correct 1022 ms 166648 KB Output is correct
35 Correct 607 ms 107388 KB Output is correct
36 Correct 662 ms 114800 KB Output is correct
37 Correct 712 ms 126456 KB Output is correct
38 Correct 1084 ms 192504 KB Output is correct
39 Correct 808 ms 144520 KB Output is correct
40 Correct 1068 ms 194040 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 13 ms 2048 KB Output is correct
3 Correct 14 ms 2304 KB Output is correct
4 Correct 8 ms 512 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 12 ms 1920 KB Output is correct
7 Correct 13 ms 2048 KB Output is correct
8 Correct 14 ms 2304 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 13 ms 2176 KB Output is correct
11 Correct 14 ms 2304 KB Output is correct
12 Correct 8 ms 1152 KB Output is correct
13 Correct 649 ms 156164 KB Output is correct
14 Correct 420 ms 100600 KB Output is correct
15 Correct 433 ms 107488 KB Output is correct
16 Correct 469 ms 117112 KB Output is correct
17 Correct 565 ms 136444 KB Output is correct
18 Correct 751 ms 181368 KB Output is correct
19 Correct 498 ms 120952 KB Output is correct
20 Correct 554 ms 99628 KB Output is correct
21 Correct 670 ms 121976 KB Output is correct
22 Correct 780 ms 144632 KB Output is correct
23 Correct 712 ms 149112 KB Output is correct
24 Correct 723 ms 134696 KB Output is correct
25 Correct 741 ms 134776 KB Output is correct
26 Correct 555 ms 101192 KB Output is correct
27 Correct 701 ms 129136 KB Output is correct
28 Correct 699 ms 127608 KB Output is correct
29 Correct 900 ms 165132 KB Output is correct
30 Correct 739 ms 135588 KB Output is correct
31 Correct 640 ms 119032 KB Output is correct
32 Correct 589 ms 19288 KB Output is correct
33 Correct 337 ms 9848 KB Output is correct
34 Correct 355 ms 10380 KB Output is correct
35 Correct 529 ms 14028 KB Output is correct
36 Correct 522 ms 13944 KB Output is correct
37 Correct 533 ms 14456 KB Output is correct
38 Correct 699 ms 20984 KB Output is correct
39 Correct 15 ms 2304 KB Output is correct
40 Incorrect 13 ms 1920 KB Output isn't correct
41 Halted 0 ms 0 KB -