oj.uz

Submission #915665

# Submission time Handle Problem Language Result Execution time Memory
915665 2024-01-24T13:58:24 Z Whisper Skyline (IZhO11_skyline) C++17
0 / 100
 82 ms 99740 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[MAX];

int dp[301][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 = INF;
    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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 99412 KB Output is correct
2 Correct 28 ms 99360 KB Output is correct
3 Correct 29 ms 99408 KB Output is correct
4 Correct 28 ms 99408 KB Output is correct
5 Correct 30 ms 99408 KB Output is correct
6 Correct 27 ms 99420 KB Output is correct
7 Correct 27 ms 99448 KB Output is correct
8 Correct 28 ms 99416 KB Output is correct
9 Correct 29 ms 99416 KB Output is correct
10 Correct 29 ms 99276 KB Output is correct
11 Correct 39 ms 99664 KB Output is correct
12 Correct 32 ms 99408 KB Output is correct
13 Correct 42 ms 99676 KB Output is correct
14 Correct 48 ms 99740 KB Output is correct
15 Incorrect 82 ms 99536 KB Output isn't correct
16 Halted 0 ms 0 KB -