Submission #1247859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247859		vlomaczk	Stove (JOI18_stove)	C++20	50 / 100	145 ms	327680 KiB

stove

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n, k;
	cin >> n >> k;
	vector<ll> T(n+1);
	for(int i=1; i<=n; ++i) cin >> T[i];
	ll inf = 1e15;
	vector<vector<ll>> dp(n+1, vector<ll>(k+1, inf));
	dp[0][0] = 0;
	for(int i=1; i<=n; ++i) {
		int d = T[i]-T[i-1];
		for(int x=1; x<=k; ++x) {
			dp[i][x] = min(dp[i-1][x] + d, dp[i-1][x-1]+1);
		}
	}
	cout << dp[n][k] << "\n";

	return 0;
}

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