Submission #90670

#	Time	Username	Problem	Language	Result	Execution time	Memory
90670		P1QG	K blocks (IZhO14_blocks)	C++11	100 / 100	291 ms	42460 KiB

blocks

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

int n, k, a[maxn], F[maxn][105];

int main()
{
    //freopen("BLOCKS.inp","r",stdin);
    //freopen("BLOCKS.out","w",stdout);

    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++) F[i][j] = 1e9+9;
    }

    F[0][1] = 0;
    for(int i=1;i<=n;i++) F[i][1] = max(F[i-1][1], a[i]);

    for(int i=2;i<=k;i++)
    {
        stack< pair<int,int> > P;
        for(int j=i;j<=n;j++)
        {
            int cur = F[j-1][i-1];

            while(P.size() && a[P.top().second] <= a[j])
            {
                cur = min(cur, P.top().first);
                P.pop();
            }

            F[j][i] = min(cur + a[j], F[P.empty() ? 0 : P.top().second][i]);

            P.push( make_pair(cur, j));
        }
    }

    cout << F[n][k];
}

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