oj.uz

Submission #899211

# Submission time Handle Problem Language Result Execution time Memory
899211 2024-01-05T15:38:55 Z Blagoj Stove (JOI18_stove) C++17
0 / 100
 0 ms 348 KB 
#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];
    sort(all(v));
    ll lb = -1e14, rb = 1e14, res = 1e14;
    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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -