Submission #979501

#	Time	Username	Problem	Language	Result	Execution time	Memory
979501		michified	Lightning Conductor (POI11_pio)	C++17	72 / 100	1049 ms	4868 KiB

pio

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, i, hi = 0;
    cin >> n;
    vector<int> h(n), ans(n), rts;
    for (i = 0; i < n; i++) cin >> h[i];
    for (i = 0; i * i < n; i++) rts.push_back(i * i);

    for (i = 0; i < n; i++) {
        for (int r : rts) {
            if (i - r <= 0) break;
            hi = max(hi, h[i - r - 1] + (int) sqrt(r) + 1);
        }
        ans[i] = max(ans[i], hi);
    }

    reverse(ans.begin(), ans.end());
    reverse(h.begin(), h.end());

    hi = 0;
    for (i = 0; i < n; i++) {
        for (int r : rts) {
            if (i - r <= 0) break;
            hi = max(hi, h[i - r - 1] + (int) sqrt(r) + 1);
        }
        ans[i] = max(ans[i], hi);
    }

    reverse(ans.begin(), ans.end());
    reverse(h.begin(), h.end());
    
    for (i = 0; i < n; i++) cout << max(0, ans[i] - h[i]) << endl;
    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: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10