Submission #785794

#	Time	Username	Problem	Language	Result	Execution time	Memory
785794		anton	K blocks (IZhO14_blocks)	C++17	100 / 100	569 ms	90992 KiB

blocks

#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int> 

const int N_MAX = 1e5;
const int K_MAX = 100;

const int INF = (1LL<<61LL)-1;
int n, k;
int dp[N_MAX+1][K_MAX+1];
int best[N_MAX+1][K_MAX+1];
int a[N_MAX];



void display(int l, int id){
    for(int i = 0; i<n; i++){
        if(id<=i && i<best[id][l]){
            cout<<'-';
        }
        else{
            cout<<' ';
        }
    }
    cout<<endl;

    if(l>1){
        display(l-1, best[id][l]);
    }
}


void find(){
    for(int left =0; left<=k; left++){
        vector<pii> item;
        vector<int> best;
        for(int i = n; i>=0; i--){
            if(left == 0){
                if( i==n){
                    dp[i][left] = 0;
                }
                else{
                    dp[i][left] = INF;
                }
            }
            else if( i == n){
                dp[i][left] = INF;
            }
            else{
                int v= dp[i+1][left-1];
                while(item.size()>0 && item.back().first<a[i]){
                    v = min(v, item.back().second);
                    item.pop_back();
                    best.pop_back();
                }
                item.push_back(pii(a[i], v));
                if(best.size()>0){
                    best.push_back(min(best.back(), v+a[i]));
                }
                else{
                    best.push_back(v+a[i]);
                }
                dp[i][left] = best.back();
            }

            

        }
    }

    cout<<dp[0][k]<<endl;

    display(k, 0);
}

signed main(){
    cin>>n>>k;

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

}

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