Submission #102689

#	Time	Username	Problem	Language	Result	Execution time	Memory
102689		stefdasca	K blocks (IZhO14_blocks)	C++14	100 / 100	189 ms	1988 KiB

blocks

/*
        IZhO 14-Blocks(same as this 2008 Romanian problem - https://www.infoarena.ro/problema/ksecv)

    We can solve it using deques, where dp[i][j] = min sum if we split the first j numbers in i sequences

*/
#include<bits/stdc++.h>
using namespace std;
int n, k, dp[3][100002], v[100002];
int val[100002], pmax[100002], pmin[100002], sz;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    int mx = 0;
    for(int i = 1; i <= n; ++i)
    {
        mx = max(mx, v[i]);
        dp[1][i] = mx;
    }
    for(int i = 2; i <= k; ++i)
    {
        sz = 0;
        for(int j = i; j <= n; ++j)
        {
            int zmin = j-1;
            while(sz && v[j] >= v[val[sz]])
            {
                if(dp[1][pmin[sz]] < dp[1][zmin])
                    zmin = pmin[sz];
                --sz;
            }
            ++sz;
            val[sz] = j;
            pmin[sz] = zmin;
            if(sz == 1)
                pmax[sz] = dp[1][zmin] + v[j];
            else
            {
                if(pmax[sz - 1] < dp[1][zmin] + v[j])
                    pmax[sz] = pmax[sz - 1];
                else
                    pmax[sz] = dp[1][zmin] + v[j];
            }
            dp[2][j] = pmax[sz];
        }
        for(int j = 1; j <= n; ++j)
            dp[1][j] = dp[2][j], dp[2][j] = 0;
    }
    cout << dp[1][n] << '\n';
    return 0;
}

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