#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MAX=5e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
int n;
int h[MAX];
ldb dp[MAX];
void cal(int l,int r,int il,int ir) {
int m=l+r>>1;
dp[m]=-INF;
int id=0;
for (int i=il;i<=ir;i++) {
if (dp[m]<h[i]+sqrt(abs(i-m))) {
dp[m]=h[i]+sqrt(abs(i-m));
id=i;
}
}
dp[m]-=h[m];
if (m+1<=r) cal(m+1,r,il,id);
if (l<=m-1) cal(l,m-1,id,ir);
}
int main() {
speed;
cin>>n;
for (int i=1;i<=n;i++) {
cin>>h[i];
}
// for (int i=1;i<=n;i++) {
// for (int j=1;j<=n;j++) {
// cout<<fixed<<setprecision(6)<<h[j]-h[i]+sqrt(abs(i-j))<<" ";
// }
// cout<<"\n";
// }
cal(1,n,1,n);
for (int i=1;i<=n;i++) {
cout<<max(0,(int)ceil(dp[i]-1e-6))<<"\n";
}
return 0;
}
Compilation message
pio.cpp: In function 'void cal(int, int, int, int)':
pio.cpp:22:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int m=l+r>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
5208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
5212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
5028 KB |
Output is correct |
2 |
Correct |
12 ms |
4952 KB |
Output is correct |
3 |
Incorrect |
18 ms |
5172 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
5216 KB |
Output is correct |
2 |
Correct |
22 ms |
4956 KB |
Output is correct |
3 |
Incorrect |
21 ms |
5724 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
8192 KB |
Output is correct |
2 |
Correct |
52 ms |
7804 KB |
Output is correct |
3 |
Incorrect |
45 ms |
8532 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
12992 KB |
Output is correct |
2 |
Correct |
69 ms |
10832 KB |
Output is correct |
3 |
Incorrect |
68 ms |
13044 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
15040 KB |
Output is correct |
2 |
Correct |
103 ms |
12120 KB |
Output is correct |
3 |
Incorrect |
95 ms |
15184 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
12708 KB |
Output is correct |
2 |
Correct |
97 ms |
12128 KB |
Output is correct |
3 |
Incorrect |
98 ms |
15240 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |