Submission #961976

#	Time	Username	Problem	Language	Result	Execution time	Memory
961976		Mike_Vu	Lightning Conductor (POI11_pio)	C++14	100 / 100	740 ms	17936 KiB

pio

#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 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10