oj.uz

Submission #540974

# Submission time Handle Problem Language Result Execution time Memory
540974 2022-03-22T05:33:41 Z LittleOrange Stove (JOI18_stove) C++17
0 / 100
 1 ms 212 KB 
#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.0

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

Subtask #2
0 / 30.0

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

Subtask #3
0 / 50.0

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