# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
853904 | 2023-09-25T12:49:17 Z | x0r | Lightning Conductor (POI11_pio) | C++17 | 1000 ms | 65536 KB |
#include <bits/stdc++.h> #define name "" #define ll long long #define ld long double #define fi first #define se second #define pll pair < ll, ll > #define pii pair < int, int > #define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZE(x) ((int)(x).size()) #define pb push_back #define mp make_pair #define lnode node * 2, l, (l + r) / 2 #define rnode node * 2 + 1, (l + r) / 2 + 1, r using namespace std; const ld EPS = 1e-9; const int INF = 1e9 + 7; const ll LINF = 1E18; const int NMAX = 5e5; const ll MOD = 1e9 + 7; const ll BASE = 2309; const int LG = 19; ll n, a[NMAX + 3], st[NMAX + 3][LG + 3]; ll get(int l, int r) { int k = __lg(r - l + 1); return max(st[l][k], st[r - (1 << k) + 1][k]); } int main() { fast; if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); } //int t; cin >> t; while (t --) sol(); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; st[i][0] = a[i]; } for (int j = 1; j <= LG; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]); for (int i = 1; i <= n; i++) { ll res = 0; for (int j = 0; i - j * j > 1; j++) { int l = max(1, i - (j + 1) * (j + 1)), r = (i - j * j - 1); res = max(res, get(l, r) + (j + 1) - a[i]); } for (int j = 0; i + j * j < n; j++) { int l = i + j * j + 1, r = min((int)n, i + (j + 1) * (j + 1)); res = max(res, get(l, r) + (j + 1) - a[i]); } cout << res << '\n'; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2396 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2648 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 9068 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 15408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 174 ms | 17232 KB | Output is correct |
2 | Correct | 165 ms | 17268 KB | Output is correct |
3 | Correct | 163 ms | 17784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 319 ms | 23476 KB | Output is correct |
2 | Correct | 328 ms | 23348 KB | Output is correct |
3 | Correct | 316 ms | 24192 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1051 ms | 48312 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 654 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 39 ms | 65536 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |