Submission #1254655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254655		thuhienne	K blocks (IZhO14_blocks)	C++20	100 / 100	116 ms	2992 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int tt;cin >> tt;while (tt--) solve();

int n,k,arr[100009];

namespace sub2 {
    bool check() {
        return n <= 20;
    }
    void solve() {
        long long ret = 1e18;
        for (int mask = 0;mask < (1 << (n - 1));mask++) if (__builtin_popcount(mask) == k - 1) {
            long long curr = 0;
            int maxval = arr[1];
            for (int i = 0;i < n - 1;i++) {
                if (mask >> i & 1) {
                    curr += maxval;
                    maxval = arr[i + 2];
                } else maxval = max(maxval,arr[i + 2]);
            }
            curr += maxval;
            ret = min(ret,curr);
        }
        cout << ret;
    }
}

namespace sub13 {
    bool check() {
        return n <= 100;
    }
    long long dp[109][109];
    void solve() {
        for (int i = 1;i <= k;i++) dp[0][i] = 1e18;
        for (int i = 1;i <= n;i++) {
            dp[i][0] = 1e18;
            for (int j = 1;j <= k;j++) {
                dp[i][j] = 1e18;
                int maxval = -1e9;
                for (int d = i;d >= 1;d--) {
                    maxval = max(maxval,arr[d]);
                    dp[i][j] = min(dp[i][j],dp[d - 1][j - 1] + maxval);
                }
            }
        }
        cout << dp[n][k];
    }
}

namespace sub4 {
    bool check() {
        return 1;
    }
    long long prev[100009],dp[100009];
    stack <pair<int,long long>> st;
    void solve() {
        for (int i = 1;i <= n;i++) {
            dp[i] = max(dp[i - 1],1ll*arr[i]);
        }
        dp[0] = 1e18;
        arr[0] = 1e9;
        for (int tt = 2;tt <= k;tt++) {
            while (st.size()) st.pop();
            st.push({0,1e18});
            for (int i = 0;i <= n;i++) prev[i] = dp[i],dp[i] = 1e18;
            for (int i = 1;i <= n;i++) {
                pair <int,long long> hien = {i,prev[i]};
                long long val = 1e18;
                while (arr[st.top().first] <= arr[i]) {
                    hien.second = min(hien.second,st.top().second);
                    val = min(val,st.top().second);
                    st.pop();
                }
                val = min(val,prev[st.top().first]);
                dp[i] = min(val + arr[i],dp[st.top().first]);
                st.push(hien);
            }
        }
        cout << dp[n];
    }
}

int main() {
  FastIO
//  MULTEST
//  freopen("blocks.inp","r",stdin);
//  freopen("blocks.out","w",stdout);
    cin >> n >> k;
    for (int i = 1;i <= n;i++) cin >> arr[i];
    if (sub2::check()) {
        sub2::solve();
        return 0;
    }
    if (sub13::check()) {
        sub13::solve();
        return 0;
    }
    if (sub4::check()) {
        sub4::solve();
        return 0;
    }
}

/*
  Nho doi vai em gay
            co gai ay ngoi duoi goc pho nen tho ...
*/

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47