oj.uz

Submission #915668

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

# Verdict Execution time Memory Grader output
1 Correct 28 ms 100688 KB Output is correct
2 Correct 29 ms 100688 KB Output is correct
3 Correct 29 ms 100696 KB Output is correct
4 Correct 29 ms 100688 KB Output is correct
5 Correct 29 ms 100692 KB Output is correct
6 Correct 29 ms 100792 KB Output is correct
7 Correct 29 ms 100696 KB Output is correct
8 Correct 28 ms 100696 KB Output is correct
9 Correct 32 ms 100696 KB Output is correct
10 Correct 32 ms 100696 KB Output is correct
11 Correct 40 ms 100956 KB Output is correct
12 Correct 32 ms 100692 KB Output is correct
13 Correct 40 ms 100876 KB Output is correct
14 Correct 50 ms 100956 KB Output is correct
15 Incorrect 82 ms 100956 KB Output isn't correct
16 Halted 0 ms 0 KB -