#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> p2;
const int N=5e5+5;
const int inf=1e9;
int n;
int h[N],dp[N];
void solvel(int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
p2 res(-inf,0);
for(int i=optl;i<=min(mid,optr);i++)res=max(res,p2(h[i]+ceil(sqrt(mid-i))-h[mid],-i));
dp[mid]=max(dp[mid],res.first);
int opt=-res.second;
solvel(l,mid-1,optl,opt);
solvel(mid+1,r,opt,optr);
}
void solver(int l,int r,int optl,int optr){
if(l>r)return;
int mid=(l+r)/2;
p2 res(-inf,0);
for(int i=max(mid,optl);i<=optr;i++)res=max(res,p2(h[i]+ceil(sqrt(i-mid))-h[mid],i));
dp[mid]=max(dp[mid],res.first);
int opt=res.second;
solver(l,mid-1,optl,opt);
solver(mid+1,r,opt,optr);
}
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n;
for(int i=1;i<=n;i++)cin >> h[i];
solvel(1,n,1,n);
solver(1,n,1,n);
for(int i=1;i<=n;i++)cout << dp[i] << "\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
2896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
2952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
2900 KB |
Output is correct |
2 |
Correct |
16 ms |
2908 KB |
Output is correct |
3 |
Incorrect |
18 ms |
3588 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
3152 KB |
Output is correct |
2 |
Correct |
37 ms |
3168 KB |
Output is correct |
3 |
Incorrect |
28 ms |
4188 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
70 ms |
4316 KB |
Output is correct |
2 |
Correct |
94 ms |
4180 KB |
Output is correct |
3 |
Incorrect |
67 ms |
6164 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
114 ms |
7100 KB |
Output is correct |
2 |
Correct |
140 ms |
5076 KB |
Output is correct |
3 |
Incorrect |
105 ms |
9296 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
158 ms |
9300 KB |
Output is correct |
2 |
Correct |
198 ms |
6144 KB |
Output is correct |
3 |
Incorrect |
160 ms |
12112 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
180 ms |
6648 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |