Submission #17449

#	Time	Username	Problem	Language	Result	Execution time	Memory
17449		azecoder	Divide and conquer (IZhO14_divide)	C++98	0 / 100	0 ms	166568 KiB

divide

#include <iostream>
#include <cstdio>

#define MAXN 100005
#define intt long long

using namespace std;

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

int main ( ) {
	
	//freopen ( "blocks.in" , "r" , stdin ) ;
	//freopen ( "blocks.out" , "w" , stdout ) ;
	
	cin >> n >> k ;
	
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	
	q[1][1] = a[1] ;
	
	dp[1][1] = a[1] ;
	
	for ( intt i = 1 ; i <= n ; i ++ ) {
		
		dp[i][1] = max ( q[i - 1][1] , a[i] ) ;
		
		q[i][1] = dp[i][1] ;
		
		for ( int v = 2 ; v <= min ( i , k ) ; v ++ ) {
			
			dp[i][v] = 5043434334 ;
			
			if ( i - 1 >= v ) {
			
				dp[i][v] = dp[i - 1][v] + max ( a[i] - q[i - 1][v] , null ) ;
			
				q[i][v] = max ( q[i - 1][v] , a[i] ) ;
			
			}
			
			if ( dp[i][v] > dp[i - 1][v - 1] + a[i] ) {
				
				dp[i][v] = dp[i - 1][v - 1] + a[i] ;
				
				q[i][v] = a[i] ;
					
			}
			
		}
			
	}
	
	cout << dp[n][k] << endl ;
	
	return 0 ;
		
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52