Submission #879328

#	Time	Username	Problem	Language	Result	Execution time	Memory
879328		KN200711	K blocks (IZhO14_blocks)	C++14	100 / 100	157 ms	41324 KiB

blocks

# include <bits/stdc++.h>
# define fi first
# define se second
using namespace std;

int dp[100001][101];
stack< pair<int, int> > S;

int main() {
	int N, K;
	scanf("%d %d", &N, &K);
	vector<int> arr(N + 1);
	for(int i=1;i<=N;i++) {
		scanf("%d", &arr[i]);
	}
	for(int i=0;i<=N;i++) {
		for(int k=0;k<=K;k++) dp[i][k] = 1e9;
	}
	dp[0][0] = 0;
	for(int k=1;k<=K;k++) {
		while(S.size()) S.pop();
		for(int c=k;c<=N;c++) {
			int res = dp[c - 1][k - 1];
		//	cout<<res<<endl;
			while(S.size() && arr[S.top().se] <= arr[c]) {
				res = min(res, S.top().fi);
				S.pop();
			}
			int j;
			if(S.size()) j = S.top().se;
			else j = 0;
			
		//	cout<<"j : "<<res<<" "<<j<<" "<<dp[j][k]<<endl;
			
			dp[c][k] = min(dp[j][k], res + arr[c]);
		//	cout<<"dp : "<<c<<" "<<k<<" "<<dp[c][k]<<endl;
			S.push(make_pair(res, c));
		}
	}
	printf("%d\n", dp[N][K]);
}

Compilation message (stderr)

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

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