제출 #89870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
89870		popovicirobert	Skyline (IZhO11_skyline)	C++14	0 / 100	2 ms	640 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 = 200;

int dp[MAXN + 1][MAXN + 1];
int h[MAXN + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for(i= 2; i <= MAXN; i++) {
        dp[0][i] = 1e9;
    }
    for(i = 1; i <= n; i++) {
        for(j = 0; j <= h[i]; j++) {
            dp[i][j] = dp[i - 1][h[i - 1]] + 3 * j;
            if(i > 1) {
                for(int k = 0; k <= min(j, h[i - 1]); k++) {
                    dp[i][j] = min(dp[i][j], dp[i - 1][h[i - 1] - k] + max(0, j - k) * 3 + max(0, h[i - 1] - k) * 3 + 5 * k);
                }
            }
            if(i > 2) {
                for(int k = 0; k <= h[i - 2]; k++) {
                    int mn = min(h[i - 2] - k, min(h[i - 1], j));
                    int a = h[i - 2] - k - mn, b = h[i - 1] - mn, c = j - mn;
                    int cur = 5 * min(a, b);
                    if(a <= b) {
                        cur += 5 * min(b - a, c);
                        cur += 3 * max(b - a - c, c - (b - a));
                    }
                    else {
                        cur += 3 * (a - b) + 3 * c;
                    }
                    dp[i][j] = min(dp[i - 2][k] + cur + 7 * mn, dp[i][j]);
                    cur = 5 * min(b, c);
                    if(b >= c) {
                        cur += 5 * min(a, b - c);
                        cur += 3 * max(a - (b - c), b - c - a);
                    }
                    else {
                        cur += 3 * (c - b) + 3 * a;
                    }
                    dp[i][j] = min(dp[i - 2][k] + cur + 7 * mn, dp[i][j]);
                }
            }
        }
    }
    cout << dp[n][h[n]];
    //cin.close();
    //cout.close();
    return 0;
}

• Subtask 1: 0 / 100