Submission #224268

#TimeUsernameProblemLanguageResultExecution timeMemory
224268bortozSolar Storm (NOI20_solarstorm)C++17
10 / 100
247 ms95200 KiB
#include "bits/stdc++.h" using namespace std; typedef long long ll; #define fi first #define se second constexpr int MAXN = 1 << 20, LOGN = 21; int J[LOGN][MAXN]; ll D[MAXN]; int C[MAXN]; int lx[MAXN], rx[MAXN]; int main() { ios::sync_with_stdio(false); cin.tie(0); int N, S; ll K; cin >> N >> S >> K; S--; for (int i = 1; i < N; i++) { cin >> D[i]; D[i] += D[i - 1]; } for (int i = 1; i <= N; i++) { cin >> C[i]; C[i] += C[i - 1]; } for (int i = 0, l = 0, r = 0, x = 0; i < N; i++) { while (r < N && D[r] <= D[i] + K) r++; while (D[l] + K < D[i]) l++; while (rx[x] < l) x++; lx[i] = l; rx[i] = r; J[0][i] = x; } for (int k = 1; k < LOGN; k++) { for (int i = 0; i < N; i++) { J[k][i] = J[k - 1][J[k - 1][i]]; } } ll res = 0; int pos = 0; for (int i = 0; i < N; i++) { int x = i; for (int k = 0; k < LOGN; k++) { if (S & 1 << k) x = J[k][x]; } ll T = C[rx[i]] - C[lx[x]]; if (T > res) { res = T; pos = i; } } vector<int> sol{pos}; for (int i = 0; pos > 0 && i < S; i++) { sol.push_back(pos = J[0][pos]); } reverse(sol.begin(), sol.end()); cout << sol.size() << '\n'; for (int i = 0; i < sol.size(); i++) { cout << sol[i] + 1 << " \n"[i + 1 == sol.size()]; } return 0; }

Compilation message (stderr)

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:69:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < sol.size(); i++) {
                   ~~^~~~~~~~~~~~
SolarStorm.cpp:70:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     cout << sol[i] + 1 << " \n"[i + 1 == sol.size()];
                                 ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...