Submission #439011

#	Time	Username	Problem	Language	Result	Execution time	Memory
439011		meatrow	Solar Storm (NOI20_solarstorm)	C++17	100 / 100	1984 ms	157736 KiB

SolarStorm

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
const int MOD = 998244353;
 
ll binpow(ll a, ll p, int mod = MOD) {
    ll res = 1;
    while (p) {
        if (p & 1) {
            (res *= a) %= mod;
        }
        p >>= 1;
        (a *= a) %= mod;
    }
    return res;
}
 
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int s, n;
    ll k;
    cin >> n >> s >> k;
    vector<ll> pos(n + 1);
    pos[0] = -1;
    for (int i = 2; i <= n; i++) {
        cin >> pos[i];
        pos[i] += pos[i - 1];
    }
    vector<ll> value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> value[i];
        value[i] += value[i - 1];
    }
    const int K = 21;
    vector<vector<int>> go(n + 2, vector<int>(K));
    go[n + 1].assign(K, n + 1);
    ll best_value = -1;
    ll start = 0;
    for (int i = n; i >= 1; i--) {
        int mid = upper_bound(pos.begin(), pos.end(), pos[i] + k) - pos.begin() - 1;
        int lst = upper_bound(pos.begin(), pos.end(), pos[mid] + k) - pos.begin();
        go[i][0] = lst;
        for (int j = 1; j < K; j++) {
            go[i][j] = go[go[i][j - 1]][j - 1];
        }
        int cur = i;
        for (int j = K - 1; j >= 0; j--) {
            if (s >> j & 1) {
                cur = go[cur][j];
            }
        }
        ll cur_value = value[cur - 1] - value[i - 1];
        if (cur_value > best_value) {
            best_value = cur_value;
            start = i;
        } 
    }

    vector<int> ans;
    while (s && start <= n) {
        int mid = upper_bound(pos.begin(), pos.end(), pos[start] + k) - pos.begin() - 1;
        ans.push_back(mid);
        start = go[start][0];
        s--;
    }
    cout << ans.size() << endl;
    for (int i : ans) {
        cout << i << ' ';
    }
    cout << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        // cout << "Case #" << tc << ": ";
        solve();
    }
    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