oj.uz

Submission #17449

# Submission time Handle Problem Language Result Execution time Memory
17449 2015-12-13T13:34:07 Z azecoder Divide and conquer (IZhO14_divide) C++
0 / 100
 0 ms 166568 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 166568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 166568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 52.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 166568 KB Output isn't correct
2 Halted 0 ms 0 KB -