oj.uz

Submission #445802

# Submission time Handle Problem Language Result Execution time Memory
445802 2021-07-19T15:38:17 Z iulia13 Skyline (IZhO11_skyline) C++14
100 / 100
 72 ms 50616 KB 
#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9 + 5;
const int N = 305;
const int H = 205;
int dp[N][H][H]; ///dp[i][j][k] = sunt la cladirea i iar pe i mai am j iar pe i-1 mai am k
int h[N];
int main()
{
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> h[i];
    memset(dp, INF, sizeof dp);
    for (i = 0; i <= h[1]; i++)
        dp[2][h[2]][i] = dp[1][i][0] = 3 * (h[1] - i);
    for (i = 2; i <= n; i++)
    {
        for (j = h[i]; 0 <= j; j--)
            for (k = h[i - 1]; 0 <= k; k--)
                dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k] + 3);
        for (j = h[i]; 0 <= j; j--)
            for (k = h[i - 1]; 0 <= k; k--)
                dp[i][j][k] = min(dp[i][j][k], dp[i][j + 1][k + 1] + 5);
        for (int l = min(h[i + 1], min(h[i], h[i - 1])); 0 <= l; l--) ///atateam am scos din v[i - 1] ca tb sa l fac 0
            for (j = h[i]; l <= j; j--)
                dp[i + 1][h[i + 1] - l][j - l] = min(dp[i][j][l] + 7 * l, dp[i + 1][h[i + 1] - l][j - l]);
    }
    cout << dp[n][0][0];
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 50380 KB Output is correct
2 Correct 26 ms 50436 KB Output is correct
3 Correct 26 ms 50472 KB Output is correct
4 Correct 27 ms 50372 KB Output is correct
5 Correct 26 ms 50416 KB Output is correct
6 Correct 26 ms 50372 KB Output is correct
7 Correct 26 ms 50344 KB Output is correct
8 Correct 26 ms 50384 KB Output is correct
9 Correct 26 ms 50428 KB Output is correct
10 Correct 27 ms 50380 KB Output is correct
11 Correct 31 ms 50364 KB Output is correct
12 Correct 27 ms 50440 KB Output is correct
13 Correct 32 ms 50344 KB Output is correct
14 Correct 35 ms 50380 KB Output is correct
15 Correct 56 ms 50448 KB Output is correct
16 Correct 58 ms 50616 KB Output is correct
17 Correct 72 ms 50440 KB Output is correct
18 Correct 70 ms 50376 KB Output is correct
19 Correct 69 ms 50444 KB Output is correct
20 Correct 72 ms 50380 KB Output is correct