Submission #1307580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307580		ndn_it81	Solar Storm (NOI20_solarstorm)	C++20	36 / 100	520 ms	235324 KiB

SolarStorm

#include <bits/stdc++.h>
#define int long long
#define fr(i,a,n) for(int i=a;i<=n;i++)
#define fx(i,a,b) for(int i=a;i>=b;i--)
#define endl "\n"
#define FILE "name"
using namespace std;
const int N=1e6+6;
const int mod=1e9+7;
const int inf=INT_MAX;
int nxt[N][25];
int x[N],v[N];
int vt[N];
int cnt[N];
void sol(){
    int n,k,r;
    cin>>n>>k>>r;
    x[1]=0;
    fr(i,1,n-1){
        int d; cin>>d;
        x[i+1]=x[i]+d;
    }
    fr(i,1,n){
        cin>>v[i];
        cnt[i]=cnt[i-1]+v[i];
    }
    int idx=1;
    int j=1;
    fr(i,1,n){
        while(idx+1<=n&&x[idx+1]<=x[i]+r){
            ++idx;
        }
        if(j<idx) j=idx;
        while(j+1<=n&&x[j+1]<=x[idx]+r){
            ++j;
        }
        vt[i]=idx;
        nxt[i][0]=j+1;
    }
    fr(p,1,20){
        nxt[n+1][p]=n+1;
    }
    fr(p,1,20){
        fr(i,1,n){
            nxt[i][p]=nxt[nxt[i][p-1]][p-1];
        }
    }
    int ans=0;
    int L=1,R=1;
    fr(i,1,n){
        int idx=i;
        int tmp=k;
        fx(p,20,0){
            if((tmp>>p)&1){
                idx = nxt[idx][p];
                if(idx>n) break;
            }
        }
        int sum=cnt[idx-1]-cnt[i-1];
        if(sum>ans){
            ans=sum;
            L=i;
            R=idx-1;
        }
    }
    vector<int>res;
    idx = L;
    while( idx <= R&&(int)res.size()<k){
        res.push_back(vt[idx]);
        idx=nxt[idx][0];
    }
    cout<<res.size()<<"\n";
    for(auto x:res) cout<<x<<" ";
}
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    if(fopen(FILE".inp","r")){
        freopen(FILE".inp","r",stdin);
        freopen(FILE".out","w",stdout);
    }
    sol();
    return 0;
}

Compilation message (stderr)

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:78:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         freopen(FILE".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
SolarStorm.cpp:79:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         freopen(FILE".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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