oj.uz

Submission #448284

# Submission time Handle Problem Language Result Execution time Memory
448284 2021-07-29T13:23:43 Z stefantaga Skyline (IZhO11_skyline) C++14
100 / 100
 73 ms 50464 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 22 ms 50380 KB Output is correct
2 Correct 22 ms 50456 KB Output is correct
3 Correct 22 ms 50344 KB Output is correct
4 Correct 21 ms 50432 KB Output is correct
5 Correct 22 ms 50420 KB Output is correct
6 Correct 22 ms 50412 KB Output is correct
7 Correct 21 ms 50376 KB Output is correct
8 Correct 22 ms 50460 KB Output is correct
9 Correct 21 ms 50440 KB Output is correct
10 Correct 23 ms 50344 KB Output is correct
11 Correct 28 ms 50464 KB Output is correct
12 Correct 28 ms 50404 KB Output is correct
13 Correct 29 ms 50456 KB Output is correct
14 Correct 33 ms 50444 KB Output is correct
15 Correct 56 ms 50456 KB Output is correct
16 Correct 51 ms 50444 KB Output is correct
17 Correct 68 ms 50440 KB Output is correct
18 Correct 73 ms 50456 KB Output is correct
19 Correct 64 ms 50440 KB Output is correct
20 Correct 69 ms 50444 KB Output is correct