# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
123593 | 2019-07-01T17:53:11 Z | MohamedAhmed04 | Lightning Conductor (POI11_pio) | C++14 | 1000 ms | 11576 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) continue ; 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) continue ; 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 | 24 ms | 1016 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 43 ms | 1400 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 1400 KB | Output is correct |
2 | Correct | 48 ms | 1360 KB | Output is correct |
3 | Correct | 57 ms | 1656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 104 ms | 2012 KB | Output is correct |
2 | Correct | 141 ms | 1912 KB | Output is correct |
3 | Correct | 102 ms | 2412 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 339 ms | 4172 KB | Output is correct |
2 | Correct | 492 ms | 3960 KB | Output is correct |
3 | Correct | 325 ms | 4692 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 630 ms | 7936 KB | Output is correct |
2 | Correct | 927 ms | 5928 KB | Output is correct |
3 | Correct | 598 ms | 7928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1052 ms | 11576 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1054 ms | 9048 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |