제출 #17458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17458		azecoder	K개의 묶음 (IZhO14_blocks)	C++98	53 / 100	1000 ms	166572 KiB

blocks

#include <iostream>

#define MAXN 100005
#define intt long long

using namespace std ;

intt n , k , a[MAXN] , dp[MAXN][105] , q[MAXN][105] ;

int main () {
	
	cin >> n >> k ;
	
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	
	for ( int i = 1 ; i <= n ; i ++ ) 
		for ( int v = 1 ; v <= k ; v ++ ) dp[i][v] = 343334344 ;
	
	dp[1][1] = a[1] ;
	
	for ( intt i = 2 ; i <= n ; i ++ ) {
		
		dp[i][1] = max ( dp[i - 1][1] , a[i] ) ;
		
		for ( int v = 2 ; v <= min ( i , k ) ; v ++ ) {
			
			intt mx = 0 ;
			
			dp[i][v] = dp[i - 1][v - 1] + a[i] ;
			
			for ( int j = i - 1 ; j >= 1 ; j -- ) {
				
				if ( j < v - 1 ) break ; 
				
				mx = max ( mx , a[j + 1] ) ;
				
				if ( dp[i][v] > dp[j][v - 1] + mx ) dp[i][v] = dp[j][v - 1] + mx ;
					
			}
				
		}
			
	}
	
	cout << dp[n][k] << endl ;
	
	return 0 ;
		
}

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