Submission #639610

#	Time	Username	Problem	Language	Result	Execution time	Memory
639610		Pietra	K blocks (IZhO14_blocks)	C++14	53 / 100	11 ms	10808 KiB

blocks

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

const int maxn = 110 ;
const int inf = 1e16 ;

int n, k, v[maxn], mx[maxn][maxn], dp[maxn][maxn][maxn] ;

int solve(int i, int j, int q){
    if(i > n) return inf ;
    if(q == k) return mx[j][n] ;
    if(dp[i][j][q] != -1) return dp[i][j][q] ;
    return dp[i][j][q] = min(solve(i+1, j, q), solve(i+1, i+1, q+1) + mx[j][i]) ;
}

int32_t main(){

    cin >> n >> k ;

    k-- ;

    for(int i = 1 ; i <= n ; i++){
        cin >> v[i] ;
    }

    memset(dp, -1, sizeof dp) ;

    for(int i = 1 ; i <= n ; i++){
        for(int j = i ; j <= n ; j++){
            int kk = 0 ;
            for(int k = i ; k <= j ; k++) kk = max(kk, v[k]) ;
            mx[i][j] = kk ;
        }
    }

    cout << solve(1, 1, 0) << "\n" ;

}

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