oj.uz

Submission #683955

# Submission time Handle Problem Language Result Execution time Memory
683955 2023-01-19T18:33:04 Z KiriLL1ca Skyline (IZhO11_skyline) C++17
100 / 100
 179 ms 222460 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define pw(x) (1ll << x)
#define vec vector
#define sz(x) (int)((x).size())
#define forn(i, s, f) for (int i = s; i <= f; ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

#define int long long

const int N = 305;
const int inf = 1e18 + 7;
int dp[N][N][N], a[N];

inline void solve () {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        if (n == 1) { cout << a[1] * 3; return; }
        forn (i, 0, N-1) forn (f, 0, N-1) forn (s, 0, N-1) dp[i][f][s] = inf;

        dp[0][0][0] = 0;
        for (int i = 0; i <= n; ++i) {
                int q = a[i + 1], w = a[i + 2];
                for (int f = 0; f <= q; ++f) {
                        for (int s = 0; s <= w; ++s) {
                                if (f == q) umin(dp[i + 1][s][0], dp[i][f][s]);
                                if (f + 1 <= q) umin(dp[i][f + 1][s], dp[i][f][s] + 3);
                                if (s + 1 <= w) umin(dp[i][f][s + 1], dp[i][f][s] + 3);
                                if (f + 1 <= q && s + 1 <= w) umin(dp[i][f + 1][s + 1], dp[i][f][s] + 5);
                                if (s + q - f <= w) umin(dp[i + 1][s + q - f][q - f], dp[i][f][s] + 7 * (q - f));
                        }
                }
        }
        cout << dp[n + 1][0][0] << endl;
}

signed main() {
        ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        #ifdef LOCAL
                freopen("input.txt", "r", stdin);
                freopen("output.txt", "w", stdout);
        #endif
        int t = 1; // cin >> t;
        while (t--) solve();
        return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 85 ms 222284 KB Output is correct
3 Correct 85 ms 222332 KB Output is correct
4 Correct 90 ms 222384 KB Output is correct
5 Correct 90 ms 222304 KB Output is correct
6 Correct 95 ms 222308 KB Output is correct
7 Correct 86 ms 222312 KB Output is correct
8 Correct 85 ms 222328 KB Output is correct
9 Correct 90 ms 222332 KB Output is correct
10 Correct 88 ms 222368 KB Output is correct
11 Correct 95 ms 222360 KB Output is correct
12 Correct 87 ms 222384 KB Output is correct
13 Correct 93 ms 222356 KB Output is correct
14 Correct 107 ms 222460 KB Output is correct
15 Correct 143 ms 222304 KB Output is correct
16 Correct 145 ms 222404 KB Output is correct
17 Correct 173 ms 222392 KB Output is correct
18 Correct 179 ms 222332 KB Output is correct
19 Correct 165 ms 222284 KB Output is correct
20 Correct 169 ms 222344 KB Output is correct