Submission #785762

#	Time	Username	Problem	Language	Result	Execution time	Memory
785762		anton	K blocks (IZhO14_blocks)	C++17	53 / 100	1080 ms	16204 KiB

blocks

#include<bits/stdc++.h>

using namespace std;
#define int long long

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++){
        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{
                dp[i][left] = INF;
                int m= 0;
                for(int j = i+1; j<=n; j++){
                    m =max(m, a[j-1]);
                    if(dp[i][left]> dp[j][left-1]+m){
                        best[i][left] = j;
                    }
                    dp[i][left] = min(dp[i][left], dp[j][left-1]+m);

                }

            }

            

        }

        for(int i = 0; i<=n; i++){
            //cout<<dp[i][left]<<" ";
        }
        //cout<<endl;
    }

    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: 0 / 47