Submission #17458

#	Time	Username	Problem	Language	Result	Execution time	Memory
17458		azecoder	K blocks (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