Submission #1124666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124666		hy_1	Stove (JOI18_stove)	C++17	100 / 100	19 ms	2244 KiB

stove

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <fstream>
#include <exception>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <climits>
#include <list>
#include <cmath>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#define int long long
#define MOD 1000000007
#define all(x) x.begin(), x.end()
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;

void solution(){
    int n,k; cin >> n >> k;
    vector<int> arr(n);
    for(int &i : arr) cin >> i;
    
    int n_ans = 1;
    int ans = 1;
    
    sort(all(arr));
    
    for(int i = 0; i < n-1; i++){
        if(arr[i+1] - arr[i] > 1){
            n_ans++;
            ans++;
        }else{
            ans++;
        }
    }
    
    vector<int> track;
    for(int  i = 0; i < n-1; i++){
        if(arr[i+1] - arr[i] > 1)
            track.push_back(arr[i+1] - arr[i] - 1);
    }
    
    sort(all(track));
    int idx = 0;
    
    // cout << ans << " " << n_ans << endl;
    
    while(n_ans > k){
        // cout << track[idx] << endl;
        ans += track[idx];
        idx++;
        n_ans -= 1;
    }
    cout << ans << endl;
}

signed main(){
    fast_io;
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solution();
    }
    return 0;
}

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