| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1091350 | Trisanu_Das | Solar Storm (NOI20_solarstorm) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int dist[N], valor[N], jump[N];
vector<int> sum, dp;
int main () {
ios::sync_with_stdio(0); cin.tie(0);
int n, s, k;
cin >> n >> s >> k;
sum.resize(n);
dp.resize(n);
for (int i = 0; i < n - 1; i++) {
cin >> dist[i];
if (i) sum[i] = sum[i - 1] + dist[i - 1];
}
for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + dist[i - 1];
for (int i = 0; i < n; i++) {
cin >> valor[i];
dp[i] += valor[i];
if (i) dp[i] += dp[i - 1];
}
int mx = -1, best_start = -1;
for (int i = 0; i < n; i++) jump[i] = upper_bound (sum.begin(), sum.end(), sum[i] + k) - sum.begin();
for (int i = 0; i < n; i++) {
int cur = 0, shield_left = s;
for (int hi = i; hi < n && shield_left > 0; ) {
int nxt = jump[hi] - 1;
int esq = dp[nxt] - (hi - 1 >= 0 ? dp[hi - 1] : 0);
cur += esq;
int nxtnxt = jump[nxt] - 1;
int dir = dp[nxtnxt] - dp[nxt];
cur += dir;
hi = nxtnxt + 1;
--shield_left;
}
if (cur > mx) {
mx = cur;
best_start = i;
}
}
vector<int> ans;
int shield_left = s;
for (int hi = best_start; hi < n && shield_left > 0; ) {
int nxt = jump[hi] - 1;
ans.emplace_back(nxt);
int nxtnxt = jump[nxt] - 1;
hi = nxtnxt + 1;
--shield_left;
}
cout << (int) ans.size() << '\n';
for (auto to : ans) cout << to + 1 << ' ';
}