#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
//const ll mod = 1e9+7;
bool maximize(ll &x, ll y ){
if (x < y) {x = y; return true;};
return false;
}
bool minimize(ll &x, ll y){
if (x > y) {x = y; return true;}
return false;
}
//void add(ll &x, ll y ){
// x += y;
// if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
// x -= y;
// if (x < 0) x += mod;
//}
const int maxn = 5e5+5;
int n;
ll a[maxn], ans[maxn] = {0};
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll temp = 0;
for (int i = 1; i <= n; i++) {
for (int k = 1; i- (k-1)*(k-1)-1 > 0; k++) {
maximize(temp, a[i-(k-1)*(k-1)-1]+k);
}
maximize(ans[i], temp);
}
temp = 0;
for (int i = n; i > 0; i-- ){
for (int k = 1; i+ (k-1)*(k-1)+1 <= n; k++) {
maximize(temp, a[i+(k-1)*(k-1)+1]+k);
}
maximize(ans[i], temp);
}
for (int i= 1; i <= n; i++) {
cout << max(0LL, ans[i]-a[i]) << "\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2768 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
3160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
26 ms |
5804 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
5940 KB |
Output is correct |
2 |
Correct |
34 ms |
5376 KB |
Output is correct |
3 |
Correct |
34 ms |
5716 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
6600 KB |
Output is correct |
2 |
Correct |
62 ms |
6480 KB |
Output is correct |
3 |
Correct |
61 ms |
6740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
216 ms |
9576 KB |
Output is correct |
2 |
Correct |
236 ms |
9124 KB |
Output is correct |
3 |
Correct |
219 ms |
9184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
421 ms |
13808 KB |
Output is correct |
2 |
Correct |
414 ms |
11816 KB |
Output is correct |
3 |
Correct |
416 ms |
12604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
700 ms |
17936 KB |
Output is correct |
2 |
Correct |
691 ms |
15184 KB |
Output is correct |
3 |
Correct |
722 ms |
16112 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
715 ms |
15440 KB |
Output is correct |
2 |
Correct |
740 ms |
15064 KB |
Output is correct |
3 |
Correct |
728 ms |
16208 KB |
Output is correct |