oj.uz

Submission #423734

# Submission time Handle Problem Language Result Execution time Memory
423734 2021-06-11T12:08:15 Z Apiram Stove (JOI18_stove) C++14
0 / 100
 1 ms 204 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;cin>>n>>k;
    vector<int64_t>arr(n);
    for (int i =0;i<n;++i){
        cin>>arr[i];
    }
    --k;
    sort(arr.begin(),arr.end());
    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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 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 204 KB Output is correct
2 Incorrect 1 ms 204 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 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -