oj.uz

Submission #915669

# Submission time Handle Problem Language Result Execution time Memory
915669 2024-01-24T14:03:30 Z Whisper Skyline (IZhO11_skyline) C++17
100 / 100
 150 ms 101224 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using T = tuple<ll, ll, ll>;

#define int long long
#define Base 41
#define sz(a) (int)a.size()
#define FOR(i, a, b) for ( int i = a ; i <= b ; i++ )
#define FORD(i, a, b) for (int i = b; i >= a; i --)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPD(i, n) for (int i = n - 1; i >= 0; --i)
#define all(x) x.begin() , x.end()
#define pii pair<int , int>
#define fi first
#define se second
#define Lg(x) 31 - __builtin_clz(x)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int MAX = 200 + 5;
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void setupIO(){
    #define name "Whisper"
    //Phu Trong from Nguyen Tat Thanh High School for gifted student
    srand(time(NULL));
    cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    cout << fixed << setprecision(10);
}

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int N;
int a[305];

int dp[305][MAX][MAX];
//dp(i, h1, h2) xét đến vị trí i độ dài của (i - 1) và (i - 2) còn dư lại là h1 và h2

int f(int pos, int h1, int h2){
    if (pos > N){
        return min(h1, h2) * 5 + (max(h1, h2) - min(h1, h2)) * 3;
    }
    int &res = dp[pos][h1][h2];
    if (~res) return res;
    res = LINF;
    int minHeight = min({h1, h2, a[pos]});
    if (minHeight == h2){
        minimize(res, f(pos + 1, a[pos] - h2, h1 - h2) + h2 * 7);
    }
    if (min(h1, h2) > 0){
        minimize(res, f(pos, h1 - 1, h2 - 1) + 5);
    }
    if (h2){
        minimize(res, f(pos, h1, h2 - 1) + 3);
    }
    return res;
}
void Whisper(){
    cin >> N;
    for (int i = 1; i <= N; ++i) cin >> a[i];
    //nhận xét 1: càng sơn nhiều thằng 1 lúc càng tối ưu
    memset(dp, -1, sizeof dp);
    cout << f(3, a[2], a[1]);
}


signed main(){
    setupIO();
    int Test = 1;
//    cin >> Test;
    for ( int i = 1 ; i <= Test ; i++ ){
        Whisper();
        if (i < Test) cout << '\n';
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 100688 KB Output is correct
2 Correct 28 ms 100692 KB Output is correct
3 Correct 28 ms 100688 KB Output is correct
4 Correct 29 ms 100944 KB Output is correct
5 Correct 28 ms 100676 KB Output is correct
6 Correct 28 ms 100700 KB Output is correct
7 Correct 28 ms 100700 KB Output is correct
8 Correct 28 ms 100688 KB Output is correct
9 Correct 29 ms 100692 KB Output is correct
10 Correct 30 ms 100692 KB Output is correct
11 Correct 40 ms 100952 KB Output is correct
12 Correct 32 ms 100688 KB Output is correct
13 Correct 40 ms 100948 KB Output is correct
14 Correct 48 ms 101140 KB Output is correct
15 Correct 106 ms 101148 KB Output is correct
16 Correct 108 ms 101224 KB Output is correct
17 Correct 150 ms 100808 KB Output is correct
18 Correct 144 ms 101084 KB Output is correct
19 Correct 133 ms 101212 KB Output is correct
20 Correct 146 ms 100940 KB Output is correct