Submission #899220

#	Time	Username	Problem	Language	Result	Execution time	Memory
899220		Blagoj	Stove (JOI18_stove)	C++17	0 / 100	1 ms	348 KiB

stove

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

ll n, k, c;
vector<ll> v;

pair<ll, ll> solve() {
    pair<ll, ll> dp[n];
    dp[0] = {1 + c, 1};
    for (int i = 1; i < n; i++) {
        ll opt1 = dp[i - 1].first + c + 1;
        ll opt2 = dp[i - 1].first + v[i] - v[i - 1];
        if (opt1 < opt2) dp[i] = {opt1, dp[i - 1].second + 1};
        else dp[i] = {opt2, dp[i - 1].second};
    }
    return dp[n - 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    ll lb = -1e16, rb = 1e16, res = 1e16;
    while (lb + 1 < rb) {
        c = (lb + rb) / 2;
        pair<ll, ll> ans = solve();
        if (ans.second > k) lb = c;
        else {
            res = min(res, ans.first - ans.second * c);
            rb = c;
        }
    }
    cout << res;
}

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