Submission #28888

#	Time	Username	Problem	Language	Result	Execution time	Memory
28888		ulna	K blocks (IZhO14_blocks)	C++11	100 / 100	213 ms	64112 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n, k;
int a[100055];

int dp[155][100055];

typedef pair<int, int> P;

#define ft first
#define sd second

P p[100055];

int main() {
	scanf("%d %d", &n, &k);

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

	memset(dp, 63, sizeof(dp));

	dp[0][0] = 0;

	for (int i = 1; i <= k; i++) {
		stack<P> sta;

		sta.push(P(0x3f3f3f3f, 0x3f3f3f3f));

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

			while (!sta.empty() && sta.top().ft <= a[j]) {
				low = min(low, sta.top().sd);
				sta.pop();
			}

			dp[i][j] = min(sta.top().ft + sta.top().sd, a[j] + low);

			if (sta.top().ft + sta.top().sd > a[j] + low) {
				sta.push(P(a[j], low));
			}
		}	
	}

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

	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
                        ^
blocks.cpp:22:21: 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