Submission #89873

#	Time	Username	Problem	Language	Result	Execution time	Memory
89873		popovicirobert	Skyline (IZhO11_skyline)	C++14	100 / 100	219 ms	64804 KiB

skyline

#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 / 100