Submission #423739

#	Time	Username	Problem	Language	Result	Execution time	Memory
423739		Apiram	Stove (JOI18_stove)	C++14	0 / 100	0 ms	204 KiB

stove

#include<bits/stdc++.h>
using namespace std;
int main(){
    int64_t n,k;cin>>n>>k;
    vector<int64_t>arr(n);
    for (int i =0;i<n;++i){
        cin>>arr[i];
    }
    --k;
    int64_t left =0,right = arr[n-1]+1;
    while(left<=right){
        int64_t mid = (right+left)>>1;
        int counts=0;
        int64_t prev = arr[0];
        for (int i =1;i<n;++i){
            if (arr[i]+1-prev>mid){
                counts++;
                prev=arr[i];
            }
        }
        if (counts>k){
            left = mid+1;
        }
        else right =  mid - 1;
    }
 
  int64_t ans= 0;
  int64_t prev =arr[0];
    for (int i =1;i<n;++i){
      if (arr[i]+1-prev>left){
        ans+=arr[i-1]+1 - prev;
      prev = arr[i];}}
  	ans+=arr[n-1]+1-prev;
    cout<<ans<<endl;
}
//2 + 4 + 3 + 2 + 1

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