oj.uz

Submission #1109818

# Submission time Handle Problem Language Result Execution time Memory
1109818 2024-11-07T17:17:12 Z Kirill22 Skyline (IZhO11_skyline) C++17
100 / 100
 47 ms 760 KB 
#include "bits/stdc++.h"

using namespace std;

const int N = 201, inf = (int) 1e9;
int dp[2][N][N], cur = 0;

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dp[cur][i][j] = inf;
        }
    }
    dp[cur][0][0] = 0;
    for (int it = 0; it < n; it++) {
        int h;
        cin >> h;
        cur ^= 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dp[cur][i][j] = inf;
            }
        }
        for (int i = 0; i <= h; i++) {
            for (int j = i; j < N; j++) {
                int res = dp[cur ^ 1][i][j] + i * 7;
                // j - i, h - i
                dp[cur][j - i][h - i] = min(dp[cur][j - i][h - i], res);
            }
        }
        for (int i = N - 1; i >= 1; i--) {
            for (int j = N - 1; j >= 1; j--) {
                dp[cur][i - 1][j - 1] = min(dp[cur][i - 1][j - 1], dp[cur][i][j] + 5);
            }
        }
        for (int i = N - 1; i >= 0; i--) {
            for (int j = N - 1; j >= 1; j--) {
                dp[cur][i][j - 1] = min(dp[cur][i][j - 1], dp[cur][i][j] + 3);
            }
        }
    }
    cout << dp[cur][0][0];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 7 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 760 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 3 ms 592 KB Output is correct
11 Correct 18 ms 604 KB Output is correct
12 Correct 4 ms 592 KB Output is correct
13 Correct 16 ms 592 KB Output is correct
14 Correct 20 ms 592 KB Output is correct
15 Correct 47 ms 592 KB Output is correct
16 Correct 44 ms 592 KB Output is correct
17 Correct 30 ms 592 KB Output is correct
18 Correct 30 ms 592 KB Output is correct
19 Correct 29 ms 592 KB Output is correct
20 Correct 38 ms 592 KB Output is correct