oj.uz

Submission #979501

# Submission time Handle Problem Language Result Execution time Memory
979501 2024-05-11T06:45:59 Z michified Lightning Conductor (POI11_pio) C++17
72 / 100
 1000 ms 4868 KB 
#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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 1212 KB Output is correct
2 Correct 141 ms 1216 KB Output is correct
3 Correct 142 ms 1428 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 1656 KB Output is correct
2 Correct 245 ms 1360 KB Output is correct
3 Correct 247 ms 2220 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 3328 KB Output is correct
2 Correct 672 ms 3068 KB Output is correct
3 Correct 706 ms 4036 KB Output is correct

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 4868 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 4184 KB Time limit exceeded
2 Halted 0 ms 0 KB -