Submission #1269830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269830		lechaa	Lightning Conductor (POI11_pio)	C++20	100 / 100	895 ms	17148 KiB

pio

#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    vector<int> pref(n);
    int mx = 0;
    for(int i = 0; i < n; i++){
        mx = max(mx, x[i]);
        pref[i] = mx;
    }
    vector<int> suf(n);
    mx = 0;
    for(int i = n-1; i >= 0; i--){
        mx = max(mx, x[i]);
        suf[i] = mx;
    }
    for(int i = 0; i < n; i++){
        int mx = 0;
        int cur = 0;
        int y = 0;
        for(int y = 1; cur <= n; y++){
            //i+cur+1, i+y*y -> y
            int c = -1e9;
            int h = -1e9;
            if(i - cur - 1 >= 0){
                c = pref[i-cur-1];
            }
            if(i+cur+1 < n){
                h = suf[i+cur+1];
            }
            //both y
            //c <= x[i] + p - y
            //c + y - x[i] = p
            mx = max(mx, c + y - x[i]);
            mx = max(mx, h + y - x[i]);
            cur = y*y;
        }
        cout << mx << "\n";
    }
    return 0;
}

• 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