oj.uz

Submission #1067297

# Submission time Handle Problem Language Result Execution time Memory
1067297 2024-08-20T14:15:54 Z TrinhKhanhDung Skyline (IZhO11_skyline) C++14
100 / 100
 56 ms 97232 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(1e9 + 19972207)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 303;

int N;
int a[MAX];
ll f[MAX][202][202];

void solve(){
    cin >> N;
    for(int i=1; i<=N; i++){
        cin >> a[i];
    }
    memset(f, 0x3f, sizeof f);
    for(int i=0; i<=a[1]; i++){
        f[1][0][a[1] - i] = f[2][a[1] - i][a[2]] = i * 3;
    }
    for(int i=2; i<=N; i++){
        for(int j=a[i - 1]; j>=0; j--){
            for(int k=a[i]; k>0; k--){
                minimize(f[i][j][k - 1], f[i][j][k] + 3);
            }
        }
        for(int j=a[i - 1]; j>0; j--){
            for(int k=a[i]; k>0; k--){
                minimize(f[i][j - 1][k - 1], f[i][j][k] + 5);
            }
        }
        if(i == N) break;
        for(int j=min(a[i - 1], min(a[i], a[i + 1])); j>=0; j--){
            for(int k=a[i]; k>=j; k--){
                minimize(f[i + 1][k - j][a[i + 1] - j], f[i][j][k] + 7LL * j);
            }
        }
    }
    cout << f[N][0][0] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen("mmgraph.inp", "r", stdin);
//    freopen("mmgraph.out", "w", stdout);

    int t = 1;
//    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 97104 KB Output is correct
2 Correct 17 ms 97232 KB Output is correct
3 Correct 16 ms 97160 KB Output is correct
4 Correct 17 ms 97116 KB Output is correct
5 Correct 17 ms 97116 KB Output is correct
6 Correct 18 ms 97116 KB Output is correct
7 Correct 16 ms 97112 KB Output is correct
8 Correct 16 ms 97196 KB Output is correct
9 Correct 16 ms 97204 KB Output is correct
10 Correct 17 ms 97196 KB Output is correct
11 Correct 21 ms 97112 KB Output is correct
12 Correct 19 ms 97116 KB Output is correct
13 Correct 20 ms 97116 KB Output is correct
14 Correct 23 ms 97116 KB Output is correct
15 Correct 47 ms 97116 KB Output is correct
16 Correct 44 ms 97112 KB Output is correct
17 Correct 56 ms 97104 KB Output is correct
18 Correct 47 ms 97108 KB Output is correct
19 Correct 47 ms 97108 KB Output is correct
20 Correct 50 ms 97172 KB Output is correct