Submission #647631

#	Time	Username	Problem	Language	Result	Execution time	Memory
647631		thanh913	K blocks (IZhO14_blocks)	C++14	100 / 100	119 ms	44152 KiB

blocks

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define multiTest unsigned long long numTest; for (cin >> numTest; numTest--;)
#define db(val) "[" #val " = " << (val) << "] "
#define el cout << '\n'
#define taskName "kblocks"

using namespace std;

typedef long long ll;
typedef pair <ll, ll> ii;

const ll si = 1e5 + 9;
const ll mod = 1e9 + 7;

int n, k, dp[109][si], a[si], lr[si], mn[si];

/*
testing someone's solution
*/

inline void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for (int i = 1; i <= n; ++i) dp[1][i] = max(dp[1][i - 1], a[i]);
    for (int i = 1; i <= n; ++i) for (lr[i] = i - 1; lr[i] && a[lr[i]] <= a[i]; ) lr[i] = lr[lr[i]];
    for (int i = 2; i <= k; ++i)
    {
        mn[i - 1] = 1e9;
        for (int j = i; j <= n; ++j)
        {
            mn[j] = dp[i - 1][j - 1];
            for (int t = j - 1; t > lr[j]; t = lr[t]) mn[j] = min(mn[j], mn[t]);
            dp[i][j] = min(dp[i][lr[j]], mn[j] + a[j]);
        }
    }
    cout << dp[k][n], el;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    multiTest
    {
        solve();
        el;
    }
}

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