Submission #167433

#TimeUsernameProblemLanguageResultExecution timeMemory
167433ThuleanxLightning Conductor (POI11_pio)C++14
81 / 100
1076 ms19396 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e5+7; int n; int h[N]; int L[N], R[N]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; memset(L,0,sizeof(L)); memset(R,0,sizeof(R)); for (int i = 0; i < n; i++) cin>>h[i]; for (int i = 0; i < n; i++) { if (i) L[i] = max(L[i], L[i-1]); for (int j = 0; i+j*j+1 < n; j++) L[i+j*j+1] = max(L[i+j*j+1], h[i] + j + 1); } reverse(h, h+n); for (int i = 0; i < n; i++) { if (i) R[i] = max(R[i], R[i-1]); for (int j = 0; i+j*j+1 < n; j++) R[i+j*j+1] = max(R[i+j*j+1], h[i] + j + 1); } reverse(h, h+n); stringstream ss; for (int i = 0; i < n; i++) ss << max(0, max(L[i], R[n-1-i]) - h[i]) << endl; cout << ss.str(); return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...