#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 998244353;
const ll MAXN = 2e5 + 100;
vector<int> h, dp1, dp2;
int sq(int x) {
int l = 0;
int r = 1000;
int ans = 1000;
while (r >= l) {
int mid = l + (r - l) / 2;
if (mid * mid >= x) {
ans = mid;
r = mid - 1;
} else
l = mid + 1;
}
return ans;
}
void dac(vector<int> &dp, int l, int r, int opt_l, int opt_r) {
if (l > r)
return ;
int mx = 0, opt = -1;
int mid = l + (r - l) / 2;
for (int now = opt_l; now <= min(mid, opt_r); now++) {
if (h[now] + sq(mid - now) > mx) {
mx = h[now] + sq(mid - now);
opt = now;
}
}
dp[mid] = mx;
dac(dp, l, mid-1, opt_l, opt);
dac(dp, mid+1, r, opt, opt_r);
}
int main() {
fast
int n;
cin >> n;
h = vector<int>(n+1);
dp1 = vector<int>(n+2);
dp2 = vector<int>(n+2);
for (int i = 1; i <= n; i++)
cin >> h[i];
dac(dp1, 1, n, 1, n);
for (int i = 1; i <= n / 2; i++)
swap(h[i], h[n-i+1]);
dac(dp2, 1, n, 1, n);
for (int i = 1; i <= n; i++)
cout << max(0, max(dp1[i], dp2[n - i + 1]) - h[n - i + 1]) << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
916 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
1308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
34 ms |
1364 KB |
Output is correct |
2 |
Correct |
30 ms |
1372 KB |
Output is correct |
3 |
Incorrect |
32 ms |
1872 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
1852 KB |
Output is correct |
2 |
Correct |
50 ms |
2624 KB |
Output is correct |
3 |
Incorrect |
48 ms |
2896 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
119 ms |
4168 KB |
Output is correct |
2 |
Correct |
116 ms |
5208 KB |
Output is correct |
3 |
Incorrect |
125 ms |
5696 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
192 ms |
7912 KB |
Output is correct |
2 |
Correct |
187 ms |
5860 KB |
Output is correct |
3 |
Incorrect |
181 ms |
9196 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
276 ms |
11184 KB |
Output is correct |
2 |
Correct |
269 ms |
8208 KB |
Output is correct |
3 |
Incorrect |
265 ms |
13028 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
272 ms |
8788 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |