Submission #229486

#	Time	Username	Problem	Language	Result	Execution time	Memory
229486		Tehillah	Stove (JOI18_stove)	C++14	100 / 100	28 ms	3324 KiB

stove

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

using ll = long long;

#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)
#define FOR(it,c) for ( __typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++ )

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 100005;
ll a[N];
int n, kk;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> kk;
    ll res = 0;
    REP(i, 0, n) {
    	cin >> a[i];    
    }
    res = a[n-1] - a[0] + 1;
    vector<ll> v;
    REP(i, 1, n) {
        v.pb(a[i] - a[i-1] - 1);
    }
    sort(all(v));
    reverse(all(v));
    REP(i, 0, kk-1) {
        res -= v[i];
    }
    cout << res << "\n";
    return 0;
}

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