Submission #92769

#	Time	Username	Problem	Language	Result	Execution time	Memory
92769		SamAnd	K blocks (IZhO14_blocks)	C++17	100 / 100	247 ms	41212 KiB

blocks

#include <iostream>
#include <stack>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005, K = 102;

int n, k;
int a[N];

int dp[K][N];
int main()
{
    //freopen("input2.txt", "r", stdin);
    //freopen("blocks.in", "r", stdin);
    //freopen("blocks.out", "w", stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];

    int maxu = 0;
    for (int j = 1; j <= n; ++j)
    {
        maxu = max(maxu, a[j]);
        dp[1][j] = maxu;
    }

    for (int i = 2; i <= k; ++i)
    {
        stack<int> s, ss, minudp;
        int minu;
        for (int j = i; j <= n; ++j)
        {
            int cminudp = dp[i - 1][j - 1];
            while (!s.empty() && a[j] >= s.top())
            {
                s.pop();
                minu = s.top();
                s.pop();
                ss.pop();
                cminudp = min(cminudp, minudp.top());
                minudp.pop();
            }
            int x = a[j] + cminudp;
            s.push(minu);
            s.push(a[j]);
            if (ss.empty())
                minu = x;
            else
                minu = min(minu, x);
            ss.push(j);
            minudp.push(cminudp);
            dp[i][j] = minu;
        }
    }

    /*for (int j = 1; j <= n; ++j)
        cout << dp[2][j] << endl;*/

    cout << dp[k][n] << endl;
    return 0;
}

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