# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29540 | 2017-07-20T05:48:03 Z | 윤교준(#1243) | Lightning Conductor (POI11_pio) | C++11 | 1000 ms | 7884 KB |
#include <bits/stdc++.h> #define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15); #define pb push_back #define sz(V) ((int)(V).size()) #define allv(V) ((V).begin()),((V).end()) #define befv(V) ((V)[sz(V)-2]) #define sorv(V) sort(allv(V)) #define revv(V) reverse(allv(V)) #define univ(V) (V).erase(unique(allv(V)),(V).end()) #define rgiv(V,n) ((V)[((n)+sz(V))%sz(V)]) #define clv(V) (V).clear() #define upmax(a,b) (a)=max((a),(b)) #define INF (0x3f3f3f3f) #define MAXN (500005) #define MAXH (1000005) using namespace std; typedef long long ll; typedef pair<int, int> pii; int SQ[MAXN]; int HL[777], HR[777]; int H[MAXN]; int P[MAXN]; int N; int main() { for(int i = 1; i <= 708; i++) { int s = (i-1)*(i-1) + 1, e = min(MAXN-1, i*i); for(int j = s; j <= e; j++) SQ[j] = i; } scanf("%d", &N); int mxh = -1; for(int i = 1; i <= N; i++) { scanf("%d", &H[i]); if(mxh < H[i]) mxh = H[i]; } int mnh = max(0, mxh-708), dh = mxh - mnh; for(int i = 1, h; i <= N; i++) { if(H[i] < mnh) continue; h = H[i] - mnh; if(!HL[h]) HL[h] = i; HR[h] = i; } for(int i = 1; i <= N; i++) { int &ret = P[i], num; for(int h = 0; h <= dh; h++) { if(!HL[h]) continue; if(HL[h] <= i) { num = h + SQ[i - HL[h]]; if(ret < num) ret = num; } if(i <= HR[h]) { num = h + SQ[HR[h] - i]; if(ret < num) ret = num; } } ret -= H[i]; ret += mnh; } for(int i = 1; i <= N; i++) printf("%d\n", P[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 166 ms | 7884 KB | Output is correct |
2 | Correct | 9 ms | 7884 KB | Output is correct |
3 | Correct | 109 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 253 ms | 7884 KB | Output is correct |
2 | Correct | 119 ms | 7884 KB | Output is correct |
3 | Correct | 146 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 619 ms | 7884 KB | Output is correct |
2 | Correct | 219 ms | 7884 KB | Output is correct |
3 | Correct | 419 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 376 ms | 7884 KB | Output is correct |
2 | Correct | 353 ms | 7884 KB | Output is correct |
3 | Correct | 873 ms | 7884 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 533 ms | 7884 KB | Output is correct |
2 | Correct | 483 ms | 7884 KB | Output is correct |
3 | Execution timed out | 1000 ms | 7884 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 7884 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |