Submission #102686

#	Time	Username	Problem	Language	Result	Execution time	Memory
102686		stefdasca	K blocks (IZhO14_blocks)	C++14	100 / 100	279 ms	2760 KiB

blocks

#include<bits/stdc++.h>
using namespace std;
int n, k, dp[3][100002], v[100002];
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)
    {
        deque<int>val;
        deque<int>pmax;
        deque<int>pmin;
        for(int j = i; j <= n; ++j)
        {
            int zmin = j-1;
            while(!val.empty() && v[j] >= v[val.back()])
            {
                if(dp[1][pmin.back()] < dp[1][zmin])
                    zmin = pmin.back();
                pmin.pop_back();
                val.pop_back();
                pmax.pop_back();
            }
            val.push_back(j);
            pmin.push_back(zmin);
            if(val.size() == 1)
                pmax.push_back(dp[1][zmin] + v[j]);
            else
            {
                if(pmax.back() < dp[1][zmin] + v[j])
                    pmax.push_back(pmax.back());
                else
                    pmax.push_back(dp[1][zmin] + v[j]);
            }
            dp[2][j] = pmax.back();
        }
        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