# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
308841 | 2020-10-02T04:52:37 Z | shivensinha4 | Lightning Conductor (POI11_pio) | C++17 | 158 ms | 14072 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]) ; int MAX = -1 ; for(int i = 0 ; i < n ; ++i) { if(arr[i] <= MAX) continue ; MAX = arr[i] ; for(int j = 1 ; i + (j-1) * (j-1) + 1 < n ; ++j) { pref[i + (j-1) * (j-1) + 1] = max(pref[i + (j-1) * (j-1) + 1] , arr[i] + j) ; } } MAX = -1 ; for(int i = n-1 ; i >= 0 ; --i) { if(arr[i] <= MAX) continue ; MAX = arr[i] ; for(int j = 1 ; i - (j-1) * (j-1) - 1 >= 0 ; ++j) { 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 | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 10 ms | 968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 1408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 1408 KB | Output is correct |
2 | Correct | 14 ms | 1408 KB | Output is correct |
3 | Correct | 19 ms | 1664 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 28 ms | 1920 KB | Output is correct |
2 | Correct | 26 ms | 1912 KB | Output is correct |
3 | Correct | 28 ms | 2424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 64 ms | 4220 KB | Output is correct |
2 | Correct | 63 ms | 3960 KB | Output is correct |
3 | Correct | 70 ms | 4600 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 114 ms | 8040 KB | Output is correct |
2 | Correct | 104 ms | 9464 KB | Output is correct |
3 | Correct | 101 ms | 9976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 158 ms | 11128 KB | Output is correct |
2 | Correct | 131 ms | 13048 KB | Output is correct |
3 | Correct | 144 ms | 14072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 154 ms | 8824 KB | Output is correct |
2 | Correct | 130 ms | 13048 KB | Output is correct |
3 | Correct | 139 ms | 14044 KB | Output is correct |