Submission #40519

#	Time	Username	Problem	Language	Result	Execution time	Memory
40519		Pajaraja	K blocks (IZhO14_blocks)	C++14	100 / 100	231 ms	13980 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
int a[100007],dp[100007],dpl[100007],minn[100007];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	a[0]=1000001;
	for(int i=1;i<=n;i++) dpl[i]=1000000000;
	stack<int> st;
	for(int z=1;z<=k;z++)
	{
		while(!st.empty()) st.pop();
		st.push(0);
		dp[0]=1000000000;
		for(int i=1;i<=n;i++)
		{
			minn[i]=1000000000;
			while(a[st.top()]<=a[i])
			{
				minn[i]=min(min(minn[i],dpl[st.top()]),minn[st.top()]);
				st.pop();
			}
			minn[i]=fmin(minn[i],dpl[st.top()]);
			dp[i]=min(dp[st.top()],minn[i]+a[i]);
			st.push(i);
		}
		for(int i=0;i<=n;i++) dpl[i]=dp[i];
	}
	printf("%d",dp[n]);
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:7:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);
                     ^
blocks.cpp:8:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
                                         ^

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