#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]+sqrt(abs(mid-best))<arr[cut]+sqrt(abs(mid-cut))){
best = cut;
}
}
dp[mid]=max(dp[mid],arr[best]+(int)ceil(sqrt(abs(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";
}
}
# |
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 |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
1508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
1584 KB |
Output is correct |
2 |
Incorrect |
26 ms |
1496 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
2208 KB |
Output is correct |
2 |
Correct |
71 ms |
2140 KB |
Output is correct |
3 |
Correct |
50 ms |
2768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
4884 KB |
Output is correct |
2 |
Correct |
143 ms |
4760 KB |
Output is correct |
3 |
Correct |
121 ms |
5412 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
231 ms |
9240 KB |
Output is correct |
2 |
Correct |
231 ms |
7276 KB |
Output is correct |
3 |
Correct |
191 ms |
9240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
327 ms |
13040 KB |
Output is correct |
2 |
Correct |
321 ms |
10096 KB |
Output is correct |
3 |
Correct |
282 ms |
13132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
10604 KB |
Output is correct |
2 |
Correct |
314 ms |
10096 KB |
Output is correct |
3 |
Correct |
270 ms |
13132 KB |
Output is correct |