oj.uz

Submission #89873

# Submission time Handle Problem Language Result Execution time Memory
89873 2018-12-18T17:26:30 Z popovicirobert Skyline (IZhO11_skyline) C++14
100 / 100
 219 ms 64804 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const int MAXN = 300;
const int MAXH = 200;

int dp[MAXN + 1][MAXH + 1][MAXH + 1];
bool vis[MAXN + 1][MAXH + 1][MAXH + 1];
int h[MAXN + 1], n;

int solve(int pos, int h1, int h2) {
    if(pos == n + 1) {
        return 0;
    }
    if(vis[pos][h1][h2]) {
        return dp[pos][h1][h2];
    }
    vis[pos][h1][h2] = 1;
    if(h1 > 0) {
        dp[pos][h1][h2] = solve(pos, h1 - 1, h2) + 3;
        if(h2 > 0) {
            dp[pos][h1][h2] = min(dp[pos][h1][h2], solve(pos, h1 - 1, h2 - 1) + 5);
        }
        if(pos < n) {
            int mn = min(h1, min(h2, h[pos + 2]));
            if(mn == h1)
                dp[pos][h1][h2] = min(dp[pos][h1][h2], solve(pos + 1, h2 - mn, h[pos + 2] - mn) + 7 * mn);
        }
    }
    else {
        dp[pos][h1][h2] = solve(pos + 1, h2, h[pos + 2]);
    }
    return dp[pos][h1][h2];
}

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> h[i];
    }
    cout << solve(1, h[1], h[2]);
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 444 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 3 ms 1784 KB Output is correct
5 Correct 2 ms 1784 KB Output is correct
6 Correct 3 ms 1784 KB Output is correct
7 Correct 3 ms 1784 KB Output is correct
8 Correct 3 ms 1784 KB Output is correct
9 Correct 4 ms 1844 KB Output is correct
10 Correct 7 ms 3440 KB Output is correct
11 Correct 33 ms 16100 KB Output is correct
12 Correct 10 ms 16100 KB Output is correct
13 Correct 31 ms 18172 KB Output is correct
14 Correct 53 ms 24960 KB Output is correct
15 Correct 142 ms 52356 KB Output is correct
16 Correct 150 ms 52356 KB Output is correct
17 Correct 219 ms 64652 KB Output is correct
18 Correct 207 ms 64652 KB Output is correct
19 Correct 204 ms 64652 KB Output is correct
20 Correct 219 ms 64804 KB Output is correct