Submission #272712

#	Time	Username	Problem	Language	Result	Execution time	Memory
272712		Killer2501	K blocks (IZhO14_blocks)	C++14	100 / 100	361 ms	82456 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "blocks"
#define fi first
#define se second
#define pll pair<ll, ll>
using namespace std;
const ll N = 1e5 + 5;
const ll mod = 1e9 + 7;
ll n, sum= 0, m, tong, k, ans, T, t;

ll a[N], dp[N][102];

char c[N];
inline void sol()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)cin >> a[i];
    for(int i = 0; i <= n; i ++)
    {
        for(int j = 0; j <= k; j ++)
            dp[i][j] = mod;
    }
    dp[0][1] = 0;
    for(int i = 1; i <= n; i ++)
    {
        dp[i][1] = max(dp[i-1][1], a[i]);
        //cout << dp[i][1] <<" ";
    }
    for(int j = 2; j <= k; j ++)
    {
        stack<pll> ds;
        for(int i = j; i <= n; i ++)
        {
            ll mn = dp[i-1][j-1];
            while(!ds.empty() && a[ds.top().se] <= a[i])
            {

                mn = min(mn, ds.top().fi);
                ds.pop();
            }
            dp[i][j] = min(dp[ds.empty() ? 0 : ds.top().se][j], mn + a[i]);
            ds.push({mn, i});
            //cout << dp[i][j] <<' ';
        }
        //cout << '\n';
    }
    cout << dp[n][k] << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sol();
  return 0;
}

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