Submission #540974

#	Time	Username	Problem	Language	Result	Execution time	Memory
540974		LittleOrange	Stove (JOI18_stove)	C++17	0 / 100	1 ms	212 KiB

stove

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,k;
vector<ll> t;
pair<ll,ll> check(ll cost){//return {price,count}
    vector<pair<ll,ll>> dp(n);//dp {price,count}
    dp[0] = {1,1};
    for (int i = 1;i<n;i++){
        if (t[i]-t[i-1]<cost){
            dp[i] = {dp[i-1].first+t[i]-t[i-1],dp[i-1].second};
        }else{
            dp[i] = {dp[i-1].first+1,dp[i-1].second+1};
        }
    }
    return dp[n-1];
}
ll run(ll l, ll r){
    if (l>=r) return check(l).first;
    ll mid = (l+r)>>1;
    if (check(mid).second<=k){
        return run(l,mid);
    }else{
        return run(mid+1,r);
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie();
    cin >> n >> k;
    t.resize(n);
    for (int i = 0;i<n;i++){
        cin >> t[i];
    }
    cout << run(0LL,1000000000000000000LL) << "\n";
}

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