Submission #224874

#	Time	Username	Problem	Language	Result	Execution time	Memory
224874		nabilervatra	Solar Storm (NOI20_solarstorm)	C++14	28 / 100	920 ms	172152 KiB

SolarStorm

#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 (stderr)

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 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30