#include <bits/stdc++.h>
using namespace std;
#define int long long
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]+sqrt(abs(mid-best))<arr[cut]+sqrt(abs(mid-cut))){
best = cut;
}
}
int val = sqrt(abs(mid-best));
double dd = sqrt((double)abs(mid-best));
if(val!=dd)val++;
dp[mid]=max(dp[mid],arr[best]+val-arr[mid]);
int opt = best;
dc(l,mid-1,optl,opt);
dc(mid+1,r,opt,optr);
}
signed 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,1,n);
reverse(arr+1,arr+n+1);
reverse(dp+1,dp+n+1);
dc(1,n,1,n);
reverse(dp+1,dp+n+1);
reverse(arr+1,arr+n+1);
for(int i = 1;i<=n;i++){
cout<<dp[i]<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
1076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
32 ms |
1504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
1612 KB |
Output is correct |
2 |
Correct |
40 ms |
1576 KB |
Output is correct |
3 |
Correct |
43 ms |
1848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
2236 KB |
Output is correct |
2 |
Correct |
65 ms |
2236 KB |
Output is correct |
3 |
Correct |
60 ms |
2752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
4968 KB |
Output is correct |
2 |
Correct |
151 ms |
4812 KB |
Output is correct |
3 |
Correct |
146 ms |
5444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
247 ms |
9204 KB |
Output is correct |
2 |
Correct |
236 ms |
7144 KB |
Output is correct |
3 |
Correct |
231 ms |
9292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
356 ms |
13064 KB |
Output is correct |
2 |
Correct |
339 ms |
10176 KB |
Output is correct |
3 |
Correct |
354 ms |
13244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
350 ms |
10648 KB |
Output is correct |
2 |
Correct |
339 ms |
10064 KB |
Output is correct |
3 |
Correct |
337 ms |
13124 KB |
Output is correct |