Submission #683481

#	Time	Username	Problem	Language	Result	Execution time	Memory
683481		nifeshe	Skyline (IZhO11_skyline)	C++17	100 / 100	314 ms	222536 KiB

skyline

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 300 + 5;
const int lg = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

int dp[MAX][MAX][MAX];

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }
    if(n == 1) {
        cout << a[0] * 3 << '\n';
        return;
    }
    for(int i = 0; i < MAX; i++) {
        for(int j = 0; j < MAX; j++) {
            for(int k = 0; k < MAX; k++) {
                dp[i][j][k] = inf;
            }
        }
    }
    dp[0][0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < MAX; j++) {
            for(int k = 0; k < MAX; k++) {
                if(j == a[i]) umin(dp[i + 1][k][0], dp[i][j][k]);
                if(j + 1 < MAX) umin(dp[i][j + 1][k], dp[i][j][k] + 3);
                if(k + 1 < MAX) umin(dp[i][j][k + 1], dp[i][j][k] + 3);
                if(j + 1 < MAX && k + 1 < MAX) umin(dp[i][j + 1][k + 1], dp[i][j][k] + 5);
                if(j < a[i] && k + (a[i] - j) < MAX) umin(dp[i + 1][k + (a[i] - j)][(a[i] - j)], dp[i][j][k] + 7 * (a[i] - j));
            }
        }
    }
    cout << dp[n][0][0] << '\n';
}

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

skyline.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

• Subtask 1: 100 / 100