# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29543 | 2017-07-20T05:50:17 Z | 윤교준(#1243) | Lightning Conductor (POI11_pio) | C++11 | 1000 ms | 13256 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; static unsigned char str[5500055], *p = str; int SQ[MAXN]; int HL[777], HR[777]; int H[MAXN]; int P[MAXN]; int N; int main() { fread(str, 1, 5500055, stdin); 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; } rf(N) int mxh = -1; for(int i = 1; i <= N; i++) { rf(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 = 0, num; //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; printf("%d\n", ret); } //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 | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 126 ms | 13256 KB | Output is correct |
2 | Correct | 3 ms | 13256 KB | Output is correct |
3 | Correct | 66 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 196 ms | 13256 KB | Output is correct |
2 | Correct | 86 ms | 13256 KB | Output is correct |
3 | Correct | 116 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 479 ms | 13256 KB | Output is correct |
2 | Correct | 203 ms | 13256 KB | Output is correct |
3 | Correct | 309 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 293 ms | 13256 KB | Output is correct |
2 | Correct | 279 ms | 13256 KB | Output is correct |
3 | Correct | 646 ms | 13256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 429 ms | 13256 KB | Output is correct |
2 | Correct | 413 ms | 13256 KB | Output is correct |
3 | Execution timed out | 1000 ms | 13256 KB | Execution timed out |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1000 ms | 13256 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |