Submission #485354

#	Time	Username	Problem	Language	Result	Execution time	Memory
485354		silverfox	K blocks (IZhO14_blocks)	C++14	100 / 100	336 ms	81592 KiB

blocks

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

const long long maxn = 1e5;
const long long maxk = 1e2;

long long a[maxn+1];
long long f[maxn+1][maxk+1];

const long long oo = 1e16;

int main()
{
    long long n,k; cin >> n >> k;
    for (long long 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] = +oo;}
    }

    /*for (long long i = 1; i <= k; i++)
    {
        if (i == 1) {f[1][i] = a[1];} else {f[1][i] = +oo;}
    }*/

    /*for (long long i = 0; i <= k; i++)
    {
        f[0][i] = +oo;
    }

    long long totalMax = -1;
    for (long long i = 1; i <= n; i++)
    {
        totalMax = max(totalMax, a[i]);
        for (long long j = 1; j <= k; j++)
        {
            f[i][j] = +oo;
            if (j > i) {continue;}

            if (j == 1)
            {
                f[i][j] = totalMax; continue;
            }

            long long curMax = a[i];
            for (long long x = i-1; x >= 1; x--)
            {
                f[i][j] = min(f[i][j], f[x][j-1] + curMax);
                curMax = max(curMax, a[x]);
            }
        }
    }
    cout << f[n][k];*/

    long long curMax = -1;
    for (long long i = 1; i <= n; i++)
    {
        curMax = max(curMax, a[i]);
        f[i][1] = curMax;
    }

    for (long long i = 2; i <= k; i++)
    {
        stack<long long> l, s2;
        for (long long j = 1; j <= n; j++)
        {
            long long cur = f[j-1][i-1];
            while(!l.empty() && l.top() < a[j])
            {
                cur = min(cur, s2.top());
                l.pop(); s2.pop();
            }
            if (l.empty() || cur + a[j] < l.top() + s2.top())
            {
                l.push(a[j]); s2.push(cur);
            }

            if (j >= i) {f[j][i] = l.top() + s2.top();}
        }
    }

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

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