Submission #1050964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050964		ivopav	K blocks (IZhO14_blocks)	C++17	100 / 100	215 ms	41684 KiB

blocks

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

int main(){
    int n;
    int k;
    cin >> n >> k;
    vector<vector<int>> dp(k+1,vector<int>(n+1,1e9));
    vector<int> lis={};
    for (int i=0;i<n;i++){
        int unos;
        cin >> unos;
        lis.push_back(unos);
    }
    dp[0][0]=0;
    for (int i=0;i<k;i++){
        stack<pair<int,int>> monsta={};
        stack<pair<int,int>> monsta2={};
        for (int j=0;j<n;j++){
          //  cout << i << " " << j << "\n";
            int sad=lis[j];
            int najm=dp[i][j];
            while (monsta.size()>0 && monsta.top().first<sad){
                najm=min(najm,monsta.top().second);
                if (monsta2.size()>0 && monsta2.top().first==monsta.top().first){
                    monsta2.pop();
                }
                monsta.pop();
            }
            if (monsta2.size()==0 || najm+sad<monsta2.top().second){
                monsta2.push({sad,najm+sad});
            }
            monsta.push({sad,najm});
            dp[i+1][j+1]=monsta2.top().second;
            
        }
    }
    cout << dp[k][n] << "\n";
}

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