Submission #362006

#	Time	Username	Problem	Language	Result	Execution time	Memory
362006		Lawliet	K blocks (IZhO14_blocks)	C++17	100 / 100	166 ms	41400 KiB

blocks

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

const int MAXK = 110;
const int MAXN = 100010;
const int INF = 1000000010;

int n, k;

int v[MAXN];
int dp[MAXK][MAXN];

vector<int> value;
vector<int> minDp;

void solveTestCase()
{
	scanf("%d %d",&n,&k);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	dp[0][0] = 0;

	for(int i = 1 ; i <= n ; i++)
		dp[0][i] = INF;

	for(int i = 1 ; i <= k ; i++)
	{
		value.clear();
		minDp.clear();

		dp[i][0] = INF;

		for(int j = 1 ; j <= n ; j++)
		{
			int curMn = dp[i - 1][j - 1];

			while( !value.empty() && value.back() <= v[j] )
			{
				curMn = min( curMn , minDp.back() );
				minDp.pop_back(); value.pop_back();
			}

			if( value.empty() || value.back() + minDp.back() > v[j] + curMn )
			{
				value.push_back( v[j] );
				minDp.push_back( curMn );
			}

			dp[i][j] = value.back() + minDp.back();
		}
	}

	printf("%d\n",dp[k][n]);
}

int main()
{
	int t = 1;
	// scanf("%d",&t);

	while( t-- )
		solveTestCase();
}

Compilation message (stderr)

blocks.cpp: In function 'void solveTestCase()':
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("%d",&v[i]);
      |   ~~~~~^~~~~~~~~~~~

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