Submission #1268129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268129		hovuviettruong	Stove (JOI18_stove)	C++17	0 / 100	0 ms	324 KiB

stove

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<ll,ll>
#define el '\n'
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
#define N 100006
using namespace std;

ll T[N];
int n, k;

pii cal(int m){

    ll cnt = 0, res = 0, pre = T[1];
    for (int i = 1; i <= n + 1; i++){
        if (T[i] + 1 - pre > m) {
            res += T[i - 1] - pre + 1;
            cnt++;
            pre = T[i];
        }
    }

    return {cnt, res};
}


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> T[i];
    }
    T[n + 1] = 1e9 + 2;

    
    ll l = 1, r = T[n] + 1, res = 1e9;
    while(l <= r){
        ll m = (l + r)/2;
        pii c = cal(m);
        if (c.fi <= k){
            res = min(res, c.se);
            r = m - 1;
        }
        else l = m + 1;
        
    }

    cout << res;







    return 0;

}

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