oj.uz

Submission #224874

# Submission time Handle Problem Language Result Execution time Memory
224874 2020-04-19T04:19:35 Z nabilervatra Solar Storm (NOI20_solarstorm) C++14
28 / 100
 920 ms 172152 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;
vector<int> ret;
int main(){
    cin>>n>>m>>k;
    for(int i =2;i<=n;i++){
        cin>>x;
        pref[i]=pref[i-1]+x;
    }
    for(int i =1;i<=n;i++){
        cin>>x;
        psum[i]=psum[i-1]+x;
    }
    p1=1;
    p2=1;
    for(int i =1;i<=n;i++){
        p1=max(p1,(long long )i);
        p2=max(p2,p1);
        while(pref[p1+1]-pref[i]<=k&&p1<n){
            p1++;
        }
        while(pref[p2+1]-pref[p1]<=k&&p2<n){
            p2++;
        }
        tab[i][0]=p2;
        // cout<<tab[i][0]<<' ';
    }
    // cout<<endl;
    for(int j =1;j<=log2(m);j++){
        for(int i =1;i<=n;i++){
            if(tab[i][j-1]==n)tab[i][j]=n;
            else tab[i][j] = tab[tab[i][j-1]+1][j-1];
            // cout<<tab[i][j]<<' ';
        }
        // cout<<endl;
    }
    for(int i=1;i<=n;i++){
        tmp= log2(m);
        cnt=m;
        now=i;
        while(cnt>0&&now<=n){
            ri = tab[now][tmp];
            now=ri+1;
            cnt-=(1<<tmp);
            tmp--;
            // if(i==2)cout<<ri<<' '<<now<<' '<<cnt<<' '<<tmp<<endl;
        }
        ans = max(ans,psum[ri]-psum[i-1]);
    }
    // cout<<ans<<endl;
    for(int i=1;i<=n;i++){
        tmp= log2(m);
        cnt=m;
        now=i;
        while(cnt>0&&now<=n){
            ri = tab[now][tmp];
            now=ri+1;
            cnt-=(1<<tmp);
            tmp--;
        }
        if(psum[ri]-psum[i-1]==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);
                while(pref[p1+1]-pref[p1]<=k&&p1<n)p1++;
                if(p1<n)p1++;
               
                cnt--;
            }
            break;
        }
    }
    cout<<ret.size()<<endl;
    for(int 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:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i =0;i<ret.size();i++){
                  ~^~~~~~~~~~~
SolarStorm.cpp:86: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 5 ms 384 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct
3 Correct 13 ms 2048 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 11 ms 1664 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 13 ms 2048 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 13 ms 2048 KB Output is correct
11 Correct 14 ms 2048 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 634 ms 148064 KB Output is correct
2 Correct 412 ms 94200 KB Output is correct
3 Correct 440 ms 101112 KB Output is correct
4 Correct 479 ms 110160 KB Output is correct
5 Correct 567 ms 129016 KB Output is correct
6 Correct 745 ms 172152 KB Output is correct
7 Correct 496 ms 113656 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct
3 Correct 13 ms 2048 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 11 ms 1664 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 13 ms 2048 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 13 ms 2048 KB Output is correct
11 Correct 14 ms 2048 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 634 ms 148064 KB Output is correct
14 Correct 412 ms 94200 KB Output is correct
15 Correct 440 ms 101112 KB Output is correct
16 Correct 479 ms 110160 KB Output is correct
17 Correct 567 ms 129016 KB Output is correct
18 Correct 745 ms 172152 KB Output is correct
19 Correct 496 ms 113656 KB Output is correct
20 Correct 549 ms 93944 KB Output is correct
21 Correct 664 ms 115192 KB Output is correct
22 Correct 772 ms 137068 KB Output is correct
23 Correct 690 ms 140920 KB Output is correct
24 Correct 733 ms 127224 KB Output is correct
25 Correct 734 ms 127352 KB Output is correct
26 Correct 553 ms 94840 KB Output is correct
27 Correct 708 ms 121848 KB Output is correct
28 Correct 690 ms 120768 KB Output is correct
29 Correct 907 ms 156720 KB Output is correct
30 Correct 742 ms 128120 KB Output is correct
31 Correct 658 ms 112376 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 828 ms 144604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct
3 Correct 13 ms 2048 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 11 ms 1664 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 13 ms 2048 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 13 ms 2048 KB Output is correct
11 Correct 14 ms 2048 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 14 ms 2048 KB Output is correct
14 Incorrect 13 ms 1664 KB Damaged module blocking communication between protected modules
15 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct
3 Correct 13 ms 2048 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 11 ms 1664 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 13 ms 2048 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 13 ms 2048 KB Output is correct
11 Correct 14 ms 2048 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 634 ms 148064 KB Output is correct
14 Correct 412 ms 94200 KB Output is correct
15 Correct 440 ms 101112 KB Output is correct
16 Correct 479 ms 110160 KB Output is correct
17 Correct 567 ms 129016 KB Output is correct
18 Correct 745 ms 172152 KB Output is correct
19 Correct 496 ms 113656 KB Output is correct
20 Correct 549 ms 93944 KB Output is correct
21 Correct 664 ms 115192 KB Output is correct
22 Correct 772 ms 137068 KB Output is correct
23 Correct 690 ms 140920 KB Output is correct
24 Correct 733 ms 127224 KB Output is correct
25 Correct 734 ms 127352 KB Output is correct
26 Correct 553 ms 94840 KB Output is correct
27 Correct 708 ms 121848 KB Output is correct
28 Correct 690 ms 120768 KB Output is correct
29 Correct 907 ms 156720 KB Output is correct
30 Correct 742 ms 128120 KB Output is correct
31 Correct 658 ms 112376 KB Output is correct
32 Correct 920 ms 150612 KB Output is correct
33 Incorrect 705 ms 115192 KB Damaged module blocking communication between protected modules
34 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 13 ms 1920 KB Output is correct
3 Correct 13 ms 2048 KB Output is correct
4 Correct 9 ms 1024 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 11 ms 1664 KB Output is correct
7 Correct 12 ms 1792 KB Output is correct
8 Correct 13 ms 2048 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 13 ms 2048 KB Output is correct
11 Correct 14 ms 2048 KB Output is correct
12 Correct 8 ms 1024 KB Output is correct
13 Correct 634 ms 148064 KB Output is correct
14 Correct 412 ms 94200 KB Output is correct
15 Correct 440 ms 101112 KB Output is correct
16 Correct 479 ms 110160 KB Output is correct
17 Correct 567 ms 129016 KB Output is correct
18 Correct 745 ms 172152 KB Output is correct
19 Correct 496 ms 113656 KB Output is correct
20 Correct 549 ms 93944 KB Output is correct
21 Correct 664 ms 115192 KB Output is correct
22 Correct 772 ms 137068 KB Output is correct
23 Correct 690 ms 140920 KB Output is correct
24 Correct 733 ms 127224 KB Output is correct
25 Correct 734 ms 127352 KB Output is correct
26 Correct 553 ms 94840 KB Output is correct
27 Correct 708 ms 121848 KB Output is correct
28 Correct 690 ms 120768 KB Output is correct
29 Correct 907 ms 156720 KB Output is correct
30 Correct 742 ms 128120 KB Output is correct
31 Correct 658 ms 112376 KB Output is correct
32 Incorrect 828 ms 144604 KB Output isn't correct
33 Halted 0 ms 0 KB -