Submission #1140721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140721		just	Stove (JOI18_stove)	C++20	100 / 100	20 ms	1996 KiB

stove

#include "bits/stdc++.h"
#include <algorithm>
using namespace std;

#ifndef debug
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#endif

#define int long long
#define all(x) (x).begin(), (x).end()
#define Tmp template<typename T>

#define len(x) ((int)((x).size()))

#define pii pair<int, int>
#define mii map <int, int>

#define yay cout<<"YES"
#define nay cout<<"NO"

#define X first
#define Y second

#define Q(x) return (void)(x)

Tmp using vec = vector<T>;

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX;
const int BIG = 1e18;

const bool Tcases = 0;
void inits() {}
void solve() {
    int n,k;
    cin>>n>>k;
    vec<int> a(n);
    for(int &x:a)cin>>x;
    sort(all(a));
    vec<int> d; d.reserve(n);
    for(int i=1;i<n;i++) d.push_back(a[i] - a[i-1] - 1);
    sort(all(d)); reverse(all(d));
    k=n-k;
    while(k--&&d.size()) {
        n += d.back(); d.pop_back();
    }
    cout<<n;
    
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin.exceptions(cin.failbit);

    #ifdef debug
    freopen("input.txt", "r", stdin);
    #endif

    __builtin_ia32_ldmxcsr(40896);

    inits();

    int t=1;
    if (Tcases) cin >> t;
    for(; t--; solve(), cout << '\n') {
        #ifdef debug
        cout << "# "; // can be also used to print case numbers
        cout.flush();
        #endif
    }
}

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