oj.uz

Submission #961976

# Submission time Handle Problem Language Result Execution time Memory
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";
    }
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2768 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2768 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3160 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5804 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory 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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory 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