Submission #1307214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307214		samarthkulkarni	Stove (JOI18_stove)	C++20	0 / 100	1 ms	568 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 n, k;
ll cost(int i, int j) {
	return a[j]+1 - a[i];
}



ll isValid(ll c) {
	ll ans = 0;
	int z = k;
	for (int i = 1; i <= n;) {
		int j = i;
		while (j <= n && cost(i, j) <= c) {
			j++;
		}
		z--;
		ans += cost(i, j-1);
		i = j;
	}

	return (z >= 0 ? ans : 0);
}


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

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


	ll p = 1, q = 1e18;
	ll ans = 1e18;
	while (p <= q) {
		ll mid = (p + q)/2;

		ll temp = isValid(mid);
		if (temp) {
			ans = temp;
			q = mid-1;
		} else p = mid+1;
	}


	cout << ans << endl;



}

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