#include <bits/stdc++.h>
using namespace std;
long long dp[500001];
long long arr[500001];
void dc(int l,int r,int optl,int optr){
if(l>r)return ;
int mid = (l+r)/2;
long long best = optl;
for(int cut = optl;cut<=min(mid,optr);cut++){
if(arr[best]+ceil(sqrt(mid-best))<arr[cut]+ceil(sqrt(mid-cut))){
best = cut;
}
}
dp[mid]=max(dp[mid],arr[best]+(long long)ceil(sqrt(mid-best)));
int opt = best;
dc(l,mid-1,optl,opt);
dc(mid+1,r,opt,optr);
}
int main(){
//ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;
cin>>n;
for(int i = 1;i<=n;i++){
cin>>arr[i];
}
for(int i = 0;i<=n;i++)dp[i] = 0;
dc(1,n,0,n-1);
reverse(arr+1,arr+n+1);
reverse(dp+1,dp+n+1);
dc(1,n,0,n-1);
reverse(dp+1,dp+n+1);
reverse(arr+1,arr+n+1);
for(int i = 1;i<=n;i++){
cout<<dp[i]-arr[i]<<"\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
1044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
1552 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
1616 KB |
Output is correct |
2 |
Incorrect |
35 ms |
1460 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
2184 KB |
Output is correct |
2 |
Correct |
73 ms |
2236 KB |
Output is correct |
3 |
Incorrect |
63 ms |
2732 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
180 ms |
4900 KB |
Output is correct |
2 |
Correct |
173 ms |
6744 KB |
Output is correct |
3 |
Incorrect |
146 ms |
6716 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
268 ms |
9240 KB |
Output is correct |
2 |
Correct |
274 ms |
10740 KB |
Output is correct |
3 |
Incorrect |
234 ms |
11320 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
382 ms |
12964 KB |
Output is correct |
2 |
Correct |
381 ms |
14924 KB |
Output is correct |
3 |
Incorrect |
331 ms |
15948 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
380 ms |
10688 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |