Submission #857723

#	Time	Username	Problem	Language	Result	Execution time	Memory
857723		DP_196	K blocks (IZhO14_blocks)	C++14	53 / 100	41 ms	852 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)

string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }

const int MAXN = 2e5 + 6;
const int INF = 1e18;
const int MOD = 1e9 + 7;

int n, k, a[MAXN], f[105][105];

void solve() {
    cin >> n >> k;

    for (int i = 1; i <= n; i++) cin >> a[i];

    memset(f, 0x3f, sizeof (f));
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        int mx = 0;
        for (int j = i; j >= 1; --j) {
            maximize(mx, a[j]);
            for (int x = 1; x <= k; x++)
                minimize(f[i][x], f[j - 1][x - 1] + mx);
        }
    }
    cout << f[n][k];
}

#define TASK ""
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();

    return 0;
}
//612

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