답안 #961976

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961976 2024-04-13T01:07:50 Z Mike_Vu Lightning Conductor (POI11_pio) C++14
100 / 100
740 ms 17936 KB
#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