Submission #375049

#	Time	Username	Problem	Language	Result	Execution time	Memory
375049		ijxjdjd	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	1386 ms	189228 KiB

SolarStorm

#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const ll INF = (ll)(1e18);
const int MAXN = (int)(1e6) + 5;
const int MAXK = 22;
set<pair<ll, int>> st;
int bk[MAXN][MAXK];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, S;
    ll K;
    cin >> N >> S >> K;
    vector<ll> loc;
    vector<ll> cost;
    cost.resize(N+1);
    loc.resize(N+1);
    loc[0] = -INF;
    cost[0] = 0;
    loc[1] = 1;
    for (int i = 2; i < N+1; i++) {
        cin >> loc[i];
        loc[i] += max(0LL, loc[i-1]);
    }
    for (int i = 1; i <= N; i++) {
        cin >> cost[i];
        cost[i] += cost[i-1];
    }
    for (int i = 0; i <= N; i++) {
        st.insert({loc[i], i});
    }
    ll res = 0;
    int resI = -1;
    for (int j = 1; j <= N; j++) {
        pair<ll, int> ini = *st.lower_bound({loc[j]-K, -1});
        ini = *(prev(st.lower_bound({ini.first-K, -1})));
        bk[j][0] = ini.second;
        for (int k = 1; k < MAXK; k++) {
            bk[j][k] = bk[bk[j][k-1]][k-1];
        }
        int cur = j;
        for (int k = 0; k < MAXK; k++) {
            if (S&(1<<k)) {
                cur = bk[cur][k];
            }
        }
        if (cost[j] - cost[cur] > res) {
            resI = j;
            res = cost[j] - cost[cur];
        }
    }
    vector<int> ans;
    FR(iter, S) {
        pair<ll, int> ini = *st.lower_bound({loc[resI]-K, -1});
        if (ini.second != 0) {
            ans.push_back(ini.second);
        }
        else {
            break;
        }
        resI = (*(prev(st.lower_bound({ini.first-K, -1})))).second;
    }
    cout << ans.size() << '\n';
    for (int j : ans) {
        cout << j << " ";
    }
	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