oj.uz

Submission #152007

# Submission time Handle Problem Language Result Execution time Memory
152007 2019-09-05T20:30:53 Z dolphingarlic Lightning Conductor (POI11_pio) C++14
100 / 100
 135 ms 11256 KB 
#include <bits/stdc++.h>
#pragma GCC Optimize("O3")
#define FOR(i, x, y) for (ll i = x; i < y; i++)
#define MOD 1000000007
typedef long long ll;
using namespace std;

int n, h[500000], dp1[500000], dp2[500000];

double slope(int j, int k) {
    double a = (k - j) / 2.0 / (h[k] - h[j]) - (h[k] - h[j]) / 2.0;
    return a * a + k;
}

void solve(int dp[]) {
    deque<int> q;
    FOR(i, 0, n) {
        if (!i || h[q.back()] < h[i]) {
            while ((q.size() > 0 && h[i] >= h[q.back()] + ceil(sqrt(i - q.back()))) ||
                   (q.size() > 1 && slope(q[q.size() - 2], q.back()) > slope(q.back(), i)))
                q.pop_back();
            q.push_back(i);
        }
        while (q.size() > 1 && slope(q[0], q[1]) < i) q.pop_front();
        dp[i] = h[q[0]] + ceil(sqrt(i - q[0]));
    }
}

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    FOR(i, 0, n) cin >> h[i];

    solve(dp1);
    FOR(i, 0, n / 2) swap(h[i], h[n - 1 - i]);
    solve(dp2);

    FOR(i, 0, n) cout << max(dp1[i], dp2[n - 1 - i]) - h[n - 1 - i] << '\n';
    return 0;
}

Compilation message

pio.cpp:2:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1404 KB Output is correct
2 Correct 13 ms 1436 KB Output is correct
3 Correct 17 ms 1656 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2040 KB Output is correct
2 Correct 26 ms 1912 KB Output is correct
3 Correct 26 ms 2524 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 4140 KB Output is correct
2 Correct 55 ms 3960 KB Output is correct
3 Correct 53 ms 4600 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 7928 KB Output is correct
2 Correct 87 ms 5880 KB Output is correct
3 Correct 85 ms 7932 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 11184 KB Output is correct
2 Correct 124 ms 8208 KB Output is correct
3 Correct 118 ms 11256 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 8704 KB Output is correct
2 Correct 122 ms 8184 KB Output is correct
3 Correct 120 ms 11132 KB Output is correct