Submission #377228

#	Time	Username	Problem	Language	Result	Execution time	Memory
377228		CaroLinda	K blocks (IZhO14_blocks)	C++14	100 / 100	195 ms	4208 KiB

blocks

#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define lp(i,a,b) for(int i = a;  i< b ; i++ )
#define pii pair<int,int> 

const int MAXN = 1e5+10 ;
const ll inf = 1e15+10LL ;

using namespace std ;

int N , K ;
int lef[MAXN] , opt[MAXN] ;
ll arr[MAXN];
ll dp[2][MAXN] ;

int main()
{
	scanf("%d %d", &N , &K ) ;
	for(int i = 1 , mx = 0  ; i <= N ; i++ ) 
	{
		scanf("%lld", &arr[i] ) ;
	
		if( arr[i] > mx ) mx = arr[i] ;
		
		dp[0][i] = mx ;

	}

	if( K == 1 ) 
	{
		printf("%lld\n", dp[0][N] ) ;
		return 0 ;
	}

	dp[0][0] = dp[1][0] = inf ;

	int toGet = 0 , toFill = 1 ;
	for(int i = 2 ;  i<= K ; i++ , swap(toGet,toFill) )
	{
		for(int j = 1 ; j <= N ; j++ )
		{
			//if I'm forming my block where I'm the maximum
			lef[j] = j-1 ;
			opt[j] = j-1 ;

			while( lef[j] && arr[j] > arr[ lef[j] ] )
			{
				if( dp[toGet][opt[lef[j]]] < dp[toGet][ opt[j] ] )
					opt[j] = opt[ lef[j] ] ;

				lef[j] = lef[ lef[j] ] ;							
			}

			//if I'm forming my block where I'm not the maximum
			if( lef[j] && dp[toFill][ lef[j] ] < dp[toGet][ opt[j] ] + arr[j] )
				dp[toFill][j] = dp[toFill][lef[j] ] ;

			else dp[toFill][j] = dp[toGet][ opt[j] ]+arr[j] ;

		}
	}

	printf("%lld\n", dp[toGet][N] ) ;
		
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |  scanf("%d %d", &N , &K ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
blocks.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |   scanf("%lld", &arr[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~

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