oj.uz

Submission #1075015

# Submission time Handle Problem Language Result Execution time Memory
1075015 2024-08-25T17:37:47 Z coolboy19521 Skyline (IZhO11_skyline) C++17
0 / 100
 105 ms 76628 KB 
#include "bits/stdc++.h"
#define ll long long

using namespace std;

const int inf = 1e5;
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;
}

int 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 'int go(int, int, int)':
skyline.cpp:26:9: warning: variable 'd' set but not used [-Wunused-but-set-variable]
   26 |     int d = -1;
      |         ^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 5980 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 0 ms 2652 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 3 ms 5780 KB Output is correct
11 Correct 19 ms 23644 KB Output is correct
12 Correct 6 ms 8284 KB Output is correct
13 Correct 20 ms 26340 KB Output is correct
14 Correct 34 ms 35920 KB Output is correct
15 Incorrect 105 ms 76628 KB Output isn't correct
16 Halted 0 ms 0 KB -