oj.uz

Submission #1075019

# Submission time Handle Problem Language Result Execution time Memory
1075019 2024-08-25T17:38:57 Z coolboy19521 Skyline (IZhO11_skyline) C++17
100 / 100
 170 ms 168092 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 2392 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 3160 KB Output is correct
8 Correct 1 ms 3420 KB Output is correct
9 Correct 2 ms 4700 KB Output is correct
10 Correct 4 ms 8132 KB Output is correct
11 Correct 21 ms 40056 KB Output is correct
12 Correct 7 ms 10760 KB Output is correct
13 Correct 27 ms 44636 KB Output is correct
14 Correct 40 ms 62568 KB Output is correct
15 Correct 141 ms 130992 KB Output is correct
16 Correct 106 ms 121424 KB Output is correct
17 Correct 157 ms 167760 KB Output is correct
18 Correct 170 ms 164260 KB Output is correct
19 Correct 149 ms 154964 KB Output is correct
20 Correct 166 ms 168092 KB Output is correct