Submission #866599

#	Time	Username	Problem	Language	Result	Execution time	Memory
866599		maks007	Stove (JOI18_stove)	C++14	20 / 100	1033 ms	23896 KiB

stove

#include "bits/stdc++.h"

using namespace std;
#define int long long
signed main () {
	int n, k;
	cin >> n >> k;
	vector <int> a(n + 1);
	for(int i = 1; i <= n; i ++) cin >> a[i];
	vector <vector <int> > dp(n + 1, vector <int> (k + 1, 1e9));
	dp[0][0] = 0;
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j <= k; j ++) {

			// dp[i][j] = min({dp[i][j], dp[i][j-1]});
			for(int I = 0; I < i; I ++)
				dp[i][j] = min(dp[I][j-1]+(a[i]-a[I+1]+1), dp[i][j]);
		}
	}
	cout << dp[n][k];
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 50