Submission #1295201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295201		k12_khoi	K blocks (IZhO14_blocks)	C++17	100 / 100	118 ms	2124 KiB

blocks

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

#define ll long long

const int N=1e5+5;
const int K=105;
const ll oo=(long double)1e18+1;

int n,k;
int a[N];

namespace sub4
{
    const int oo=1e9+1;

    int ma;
    int dp[N],opt[N];
    stack <int> st;

    void solve()
    {
        ma=0;
        for (int i=1;i<=n;i++)
        {
            ma=max(ma,a[i]);
            dp[i]=ma;
        }

        for (int rep=2;rep<=k;rep++)
        {
            while (!st.empty()) st.pop();

            for (int i=rep;i<=n;i++)
            opt[i]=dp[i-1];

            for (int i=rep;i<=n;i++)
            {
                while (!st.empty() and a[st.top()]<=a[i])
                {
                    opt[i]=min(opt[i],opt[st.top()]);
                    st.pop();
                }

                dp[i]=opt[i]+a[i];

                if (!st.empty()) dp[i]=min(dp[i],dp[st.top()]);

                st.push(i);
            }
        }

        cout << dp[n];
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

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

    sub4::solve();
}

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