Submission #1307209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307209		samarthkulkarni	Stove (JOI18_stove)	C++20	50 / 100	1096 ms	2788 KiB

stove

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

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}

const int N = 1e5+10;
ll a[N];
ll cost(int i, int j) {
	return a[j]+1 - a[i];
}

vi dp;


void dnc(int l, int r, int optl, int optr, vi &ndp) {
	if (l > r) return;
	int mid = (l + r)/2;

	int best = mid;

	for (int i = optl; i <= min(mid, optr); i++) {
		if (ndp[mid] > dp[i-1] + cost(i, mid)) {
			best = i;
			ndp[mid] = dp[i-1] + cost(i, mid);
		}
	}

	dnc(l, mid-1, optl, best, ndp);
	dnc(mid+1, r, best, optr, ndp);
}


void solution() {
	ll n, k; cin >> n >> k;

	for (int i = 1; i <= n; i++) cin >> a[i];

	dp.resize(n+1, 1e18);
	dp[0] = 0;
	for (int i = 1; i <= k; i++) {
		vi ndp(n+1, 1e18);
		dnc(1, n, 1, n, ndp);
		dp = move(ndp);
	}

	cout << dp[n] << endl;
}

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