#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,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]<<"\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 |
17 ms |
1052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
33 ms |
1568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
1612 KB |
Output is correct |
2 |
Incorrect |
38 ms |
1528 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
2200 KB |
Output is correct |
2 |
Correct |
62 ms |
2252 KB |
Output is correct |
3 |
Correct |
61 ms |
2756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
4920 KB |
Output is correct |
2 |
Correct |
156 ms |
4788 KB |
Output is correct |
3 |
Correct |
145 ms |
5432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
9288 KB |
Output is correct |
2 |
Correct |
234 ms |
7156 KB |
Output is correct |
3 |
Correct |
227 ms |
9264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
341 ms |
12988 KB |
Output is correct |
2 |
Correct |
331 ms |
10108 KB |
Output is correct |
3 |
Correct |
326 ms |
13252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
342 ms |
10736 KB |
Output is correct |
2 |
Correct |
335 ms |
10044 KB |
Output is correct |
3 |
Correct |
342 ms |
13112 KB |
Output is correct |