Submission #84672

#	Time	Username	Problem	Language	Result	Execution time	Memory
84672		farukkastamonuda	K blocks (IZhO14_blocks)	C++14	100 / 100	171 ms	51712 KiB

blocks

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define pb push_back
#define li 100005
#define ii pair<int,int>
using namespace std;
int n,k,A[li],dp[105][li];
deque< pair<int,int> > q;
int main(){
	scanf("%d %d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	for(int i=0;i<=k;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=inf;
		}
	}
	dp[0][0]=0;
	for(int i=1;i<=k;i++){
		q.clear();
		for(int j=1;j<=n;j++){
			if(i>j){
				dp[i][j]=inf;
				continue;
			}
			int s=dp[i-1][j-1];
			while(!q.empty() && q.front().fi<=A[j]){
				s=min(s,q.front().se);
				q.pop_front();
			}
			if(!q.empty() && q.front().fi+q.front().se<=s+A[j]){
				dp[i][j]=q.front().fi+q.front().se;
			}
			else{
				dp[i][j]=s+A[j];
				q.push_front(mp(A[j],s));
			}
		}
	}
	printf("%d\n",dp[k][n]);
	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:15:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
blocks.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
   ~~~~~^~~~~~~~~~~~

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