#include <bits/stdc++.h>
using namespace std;
long long dp[3001];
long long arr[3001];
void dc(int l,int r,int optl,int optr){
if(l>r)return ;
int mid = (l+r)/2;
long long best = 1e18;
for(int cut = optl;cut<=min(mid,optr+1);cut++){
if(best==1e18||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";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
436 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
460 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
468 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |