Submission #233494

#	Time	Username	Problem	Language	Result	Execution time	Memory
233494		nicolaalexandra	Stove (JOI18_stove)	C++14	100 / 100	76 ms	2168 KiB

stove

#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000000000000LL

using namespace std;
int v[DIM],dif[DIM];
int n,k,i;
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>k;
    for (i=1;i<=n;i++)
        cin>>v[i];

    if (k == 1){
        cout<<v[n]+1-v[1];
        return 0;
    }

    for (i=1;i<n;i++)
        dif[i] = v[i] - v[i+1];

    sort (dif+1,dif+n);

    long long sol = INF, sum = 0;
    for (i=1;i<k;i++){
        sum += dif[i];
        sol = min (sol,sum + v[n] - v[1] + i + 1);
    }

    cout<<sol;

    return 0;
}

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