# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
123600 | 2019-07-01T17:59:59 Z | MohamedAhmed04 | Lightning Conductor (POI11_pio) | C++14 | 247 ms | 14168 KB |
#include <bits/stdc++.h> using namespace std ; const int MAX = 5e5 + 5 ; int arr[MAX] , pref[MAX] , suff[MAX]; int n ; int main() { scanf("%d" , &n) ; for(int i = 0 ; i < n ; ++i) scanf("%d" , &arr[i]) ; for(int i = 0 ; i < n ; ++i) { for(int j = 1 ; i + (j-1) * (j-1) + 1 < n ; ++j) { if(pref[i + (j-1) * (j-1) + 1] >= arr[i] + j) break ; pref[i + (j-1) * (j-1) + 1] = max(pref[i + (j-1) * (j-1) + 1] , arr[i] + j) ; } for(int j = 1 ; i - (j-1) * (j-1) - 1 >= 0 ; ++j) { if(suff[i - (j-1) * (j-1) - 1] >= arr[i] + j) break ; suff[i - (j-1) * (j-1) - 1] = max(suff[i - (j-1) * (j-1) - 1] , arr[i] + j) ; } } for(int i = 1 ; i < n ; ++i) pref[i] = max(pref[i] , pref[i-1]) ; for(int i = n-2 ; i >= 0 ; --i) suff[i] = max(suff[i] , suff[i+1]) ; for(int i = 0 ; i < n ; ++i) printf("%d\n" , max(0 , max(pref[i] , suff[i]) - arr[i])) ; return 0 ; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 376 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 1020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 1400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 1400 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 30 ms | 1912 KB | Output is correct |
2 | Correct | 35 ms | 1920 KB | Output is correct |
3 | Incorrect | 31 ms | 2512 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 71 ms | 4088 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 120 ms | 7908 KB | Output is correct |
2 | Correct | 159 ms | 6008 KB | Output is correct |
3 | Incorrect | 103 ms | 7996 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 170 ms | 11128 KB | Output is correct |
2 | Correct | 247 ms | 13048 KB | Output is correct |
3 | Incorrect | 151 ms | 14168 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 156 ms | 8816 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |