Submission #47370

#TimeUsernameProblemLanguageResultExecution timeMemory
47370tieunhiLightning Conductor (POI11_pio)C++14
81 / 100
1076 ms22268 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define maxc 1000000007 #define N 510005 using namespace std; int n, a[N], x2[N], res[N], lef[N], rig[N]; void inline MAX(int &A, int B) {A = max(A, B);} int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= sqrt(n) + 1; i++) x2[i] = i*i; for (int i = 1; i <= n; i++) lef[i] = max(a[i], lef[i-1]); for (int i = n; i >= 1; i--) rig[i] = max(a[i], rig[i+1]); for (int i = 1; i <= n; i++) { for (int j = 1; i - x2[j-1] - 1 > 0; j++) MAX(res[i], lef[i - x2[j-1] - 1] + j); } for (int i = n; i >= 1; i--) { for (int j = 1; i + x2[j-1] + 1 <= n; j++) MAX(res[i], rig[i + x2[j-1] + 1] + j); } for (int i = 1; i <= n; i++) if (res[i] <= a[i]) cout <<0<<'\n'; else cout <<res[i] - a[i]<<'\n'; }
#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...