oj.uz

Submission #224872

# Submission time Handle Problem Language Result Execution time Memory
224872 2020-04-19T04:18:44 Z nabilervatra Solar Storm (NOI20_solarstorm) C++14
7 / 100
 826 ms 172024 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.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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 622 ms 147960 KB Output is correct
2 Correct 398 ms 94204 KB Output is correct
3 Correct 429 ms 100948 KB Output is correct
4 Correct 470 ms 110200 KB Output is correct
5 Correct 552 ms 129096 KB Output is correct
6 Correct 725 ms 172024 KB Output is correct
7 Correct 488 ms 113528 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -