oj.uz

Submission #994356

# Submission time Handle Problem Language Result Execution time Memory
994356 2024-06-07T13:14:29 Z LOLOLO Skyline (IZhO11_skyline) C++14
100 / 100
 136 ms 53660 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (ll)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 400;
int a[N], n;
int f[301][201][201];

int cal(int id, int x, int y) {
    if (id == n + 1) {
        return 0;
    }

    if (f[id][x][y] != -1)
        return f[id][x][y];

    int ans = 1e9;
    if (x == 0) {
        return f[id][x][y] = cal(id + 1, y, a[id + 2]);
    }

    ans = cal(id, x - 1, y) + 3;
    if (y) 
        ans = min(ans, cal(id, x - 1, y - 1) + 5);

    if (x <= min(y, a[id + 2])) 
        ans = min(ans, cal(id + 1, y - x, a[id + 2] - x) + x * 7);

    return f[id][x][y] = ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mem(f, -1);
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    cout << cal(1, a[1], a[2]) << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 47960 KB Output is correct
2 Correct 17 ms 47996 KB Output is correct
3 Correct 18 ms 47964 KB Output is correct
4 Correct 25 ms 47956 KB Output is correct
5 Correct 20 ms 47944 KB Output is correct
6 Correct 20 ms 47964 KB Output is correct
7 Correct 17 ms 47964 KB Output is correct
8 Correct 18 ms 47916 KB Output is correct
9 Correct 27 ms 47964 KB Output is correct
10 Correct 20 ms 48212 KB Output is correct
11 Correct 29 ms 49240 KB Output is correct
12 Correct 31 ms 48216 KB Output is correct
13 Correct 29 ms 49244 KB Output is correct
14 Correct 37 ms 50012 KB Output is correct
15 Correct 89 ms 52316 KB Output is correct
16 Correct 85 ms 52104 KB Output is correct
17 Correct 107 ms 53572 KB Output is correct
18 Correct 136 ms 53532 KB Output is correct
19 Correct 99 ms 53084 KB Output is correct
20 Correct 108 ms 53660 KB Output is correct