제출 #678028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
678028		vjudge1	Stove (JOI18_stove)	C++17	100 / 100	20 ms	3008 KiB

stove

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define PI 3.141592653589793238

using namespace std;

ll binpow (ll a, ll b){
    if (b == 0) return 1;
    if (b & 1) return binpow(a, b - 1) * a;
    else return binpow(a, b / 2) * binpow(a, b / 2);
}
ll gcd(ll a, ll b){
    return (b ? gcd(b, a % b) : a);
}
ll nums(ll g){
    ll cur = 0;
    while(g){
        cur++, g /= 10;
    }

    return cur;
}

bool comp(vector <pair <ll, ll> > a, vector <pair <ll, ll> > b){
    return a.size() < b.size();
}

ll get1(ll q, ll g){
    ll cur = 1;

    for (ll i = q; i > g; i--){
        cur *= i;
    }

    return cur;
}

const ll mod = (ll)998244353;

ll n, k, t = 1, a[200005], p[200005];

vector <ll> v;

string s;

ll dp[500][500];

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    //freopen("success.in", "r", stdin);
    //freopen("success.out", "w", stdout);

    cin >> n >> k;

    ll mn = (ll)1e15, mx = 0;

    for (ll i = 1; i <= n; i++){
        cin >> a[i];

        if (i > 1) v.pb(abs(a[i] - a[i - 1]));

        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }

    ll ans = mx - mn + 1;

    sort (v.begin(), v.end());

    ll cur = v.size() - 1;

    while(cur >= 0 && k > 1){
        ans -= (v[cur] - 1);

        cur--;
        k--;
    }

    cout << ans;

    return 0;
}

/**

4 16

10100

20
00101
10100

24



*/

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