Submission #224877

#	Time	Username	Problem	Language	Result	Execution time	Memory
224877		nabilervatra	Solar Storm (NOI20_solarstorm)	C++14	36 / 100	959 ms	172024 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;
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);
        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(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;
            else tab[i][j] = tab[tab[i][j-1]+1][j-1];
            // cout<<tab[i][j]<<' ';
        }
        // cout<<endl;
    }
    for(long long 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(long long 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(long long 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:105:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(long long i =0;i<ret.size();i++){
                        ~^~~~~~~~~~~
SolarStorm.cpp:107: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: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30