Submission #1075019

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075019		coolboy19521	Skyline (IZhO11_skyline)	C++17	100 / 100	170 ms	168092 KiB

skyline

#include "bits/stdc++.h"
#define ll long long
#define int ll

using namespace std;

const int inf = 1e18 + 18;
const int sz = 3e2 + 6;

bool vi[sz][sz][sz];
int dp[sz][sz][sz];
int h[sz];
int n;

int go(int i, int f, int s) {
    if (0 > f || 0 > s) return inf;
    int& r = dp[i][f][s];
    if (vi[i][f][s]) return r;
    vi[i][f][s] = true;
    if (0 == f) {
        if (n - 1 <= i) return 0;
        else return r = go(i + 1, s, h[i + 2]);
    }
    if (0 == s)
        return r = 3 * f + go(i + 1, s, h[i + 2]);
    r = inf;
    int d = -1;
    int k = 5 + go(i, f - 1, s - 1);
    if (k < r)
        r = k, d = 1;
    k = 3 + go(i, f - 1, s);
    if (k < r)
        r = k, d = 2;
    if (s >= f && i < n - 2 && f <= h[i + 2]) {
        k = f * 7 + go(i + 1, s - f, h[i + 2] - f);
        if (k < r)
            r = k, d = 3;
    }
    //cout << i << ' ' << f << ' ' << s << ' ' << r << ' ' << d << '\n';
    return r;
}

signed main() {
    cin >> n;

    for (int i = 0; i < n; i ++)
        cin >> h[i];

    if (1 == n)
        cout << 3 * h[0] << '\n';
    else {
        go(0, h[0], h[1]);
        cout << dp[0][h[0]][h[1]] << '\n';
    }
}

Compilation message (stderr)

skyline.cpp: In function 'long long int go(long long int, long long int, long long int)':
skyline.cpp:27:9: warning: variable 'd' set but not used [-Wunused-but-set-variable]
   27 |     int d = -1;
      |         ^

• Subtask 1: 100 / 100