Submission #687618

#	Time	Username	Problem	Language	Result	Execution time	Memory
687618		speedyArda	K blocks (IZhO14_blocks)	C++14	100 / 100	166 ms	80288 KiB

blocks

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
ll in[MAXN];
ll dp[105][MAXN];
int n, blocks;


int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> blocks;

    for(int i = 0; i < n; i++) {
        cin >> in[i];

    }
    dp[1][0] = in[0];
    for(int i = 1; i < n; i++)
       dp[1][i] = max(dp[1][i - 1], in[i]);
    //cout << "hm\n";

    for(int block = 2; block <= blocks; block++)
    {
        stack<pair<int, int> > curr;
        for(int i = block - 1; i < n; i++)
        {
            int mini = dp[block - 1][i - 1];
            while(!curr.empty() && in[curr.top().first] <= in[i])
            {
                mini = min(mini, curr.top().second);
                curr.pop();
            }


            if(curr.empty() || in[curr.top().first] + curr.top().second > in[i] + mini) 
                curr.push({i, mini});           


            dp[block][i] = in[curr.top().first] + curr.top().second;
        }
    }

    cout << dp[blocks][n - 1] << "\n";
}

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