Submission #25526

#	Time	Username	Problem	Language	Result	Execution time	Memory
25526		Bruteforceman	K blocks (IZhO14_blocks)	C++11	100 / 100	206 ms	85760 KiB

blocks

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

int a[100010];
long long dp[105][100005];
const long long inf = 1e15;

struct data {
	int val;
	long long dp, maxn;
	data (int val, long long dp, long long maxn) {
		this -> val = val;
		this -> dp = dp;
		this -> maxn = maxn;
	}
	data () {}
};

long long helpHRSiam(int N, int K, int A[]) {
	for(int i = 1; i <= N; i++) {
		a[i] = A[i-1];
	}
	memset(dp, 0, sizeof dp);
	dp[0][0] = 0;
	for(int i = 1; i <= N; i++) {
		dp[0][i] = inf;
	}
	for(int i = 1; i <= K; i++) {
		dp[i][0] = inf;
		stack <data> Q;
		for(int j = 1; j <= N; j++) {
			data x;
			x.val = a[j];
			x.dp = dp[i - 1][j - 1];
			while(!Q.empty() and Q.top().val <= a[j]) {
				x.dp = min(Q.top().dp, x.dp);
				Q.pop();
			}
			x.maxn = x.dp + x.val;
			if(!Q.empty()) x.maxn = min(x.maxn, Q.top().maxn);
			Q.push(x);
			dp[i][j] = Q.top().maxn;
		}
	}
	return dp[K][N];
}

int main(int argc, char const *argv[])
{
	int N, K;
	scanf("%d %d", &N, &K);
	int *A;
	A = new int [N];
	for(int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}
	printf("%lld\n", helpHRSiam(N, K, A));
	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main(int, const char**)':
blocks.cpp:51: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:55: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