Submission #784327

#	Time	Username	Problem	Language	Result	Execution time	Memory
784327		Cookie	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	376 ms	138420 KiB

SolarStorm

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e16;
const int mxn = 1e6 + 5;
 
int n, s; ll k;
int up[mxn + 1][20], tor[mxn + 1];
ll d[mxn + 1], pd[mxn + 1], pv[mxn + 1], v[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s >> k;
    for(int i = 2; i <= n; i++){
        cin >> d[i]; pd[i] = pd[i - 1] + d[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> v[i]; pv[i] = pv[i - 1] + v[i];
    }
    int r = 1;
    for(int i = 1; i <= n; i++){
        r = max(r, i);
        while(r <= n && pd[r] - pd[i] <= k)r++;
        tor[i] = r - 1; 
        //cout << tor[i] << " ";
    }
    for(int i = 1; i <= n; i++){
        up[i][0] = tor[tor[i]];
    }
    
    for(int i = 1; i < 20; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[min(up[j][i - 1] + 1, n)][i - 1];
        }
    }
    
    ll ans = 0, idl = 0;
    for(int i = 1; i <= n; i++){
        int r = i;
        for(int j = 0; j < 20; j++){
            if(s & (1 << j)){
                r = up[r][j] + 1;
                if(r == n + 1)break;
            }
        }
        r--;
        if(pv[r] - pv[i - 1] > ans){
            ans = pv[r] - pv[i - 1];
            idl = i;
        }
    }
    vt<int>res;
    while(idl <= n && s--){
        res.pb(tor[idl]); idl = up[idl][0] + 1;
    }
    cout << sz(res) << "\n";
    for(auto i: res){
        cout << i << " ";
    }
    return(0);
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 18 / 18
• Subtask 6: 16 / 16
• Subtask 7: 30 / 30