Submission #1306415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306415		ng.annhaat	Stove (JOI18_stove)	C++20	100 / 100	14 ms	2016 KiB

stove

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░  ░░░░░░░░   ░░░░░   ░           ░   ░░░░   ░░░░░     ░░░░░░        ░░░░
▒▒▒▒▒▒  ▒  ▒▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒▒   ▒▒▒▒   ▒▒
▒▒▒▒▒  ▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒▒   ▒▒▒▒   ▒   ▒▒▒▒▒▒▒▒   ▒   ▒▒▒▒   ▒▒
▓▓▓▓   ▓▓▓   ▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓          ▓   ▓▓▓▓▓▓▓▓   ▓  ▓   ▓▓▓▓▓▓
▓▓▓       ▓   ▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓   ▓▓▓▓▓▓▓▓   ▓   ▓▓   ▓▓▓▓
▓▓   ▓▓▓▓▓▓▓   ▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓▓   ▓▓▓▓   ▓▓▓   ▓▓▓▓▓   ▓▓   ▓▓▓▓   ▓▓
█   █████████   ███      ████████   █████   ████   █████     ██████   ██████
███████████████████████████████████████████████████████████████████████████████

         ▄▄▄      ███▄    █  ███▄    █   ██░ ██  ▄▄▄      ▄▄▄     ▄▄▄█████▓
        ▒████▄    ██ ▀█   █  ██ ▀█   █ ▒▓██░ ██ ▒████▄   ▒████▄   ▓  ██▒ ▓▒
        ▒██  ▀█▄ ▓██  ▀█ ██▒▓██  ▀█ ██▒░▒██▀▀██ ▒██  ▀█▄ ▒██  ▀█▄ ▒ ▓██░ ▒░
        ░██▄▄▄▄██▓██▒  ▐▌██▒▓██▒  ▐▌██▒ ░▓█ ░██ ░██▄▄▄▄██░██▄▄▄▄██░ ▓██▓ ░
         ▓█   ▓██▒██░   ▓██░▒██░   ▓██░ ░▓█▒░██▓ ▓█   ▓██ ▓█   ▓██  ▒██▒ ░
         ▒▒   ▓▒█░ ▒░   ▒ ▒ ░ ▒░   ▒ ▒   ▒ ░░▒░▒ ▒▒   ▓▒█ ▒▒   ▓▒█  ▒ ░░
          ░   ▒▒ ░ ░░   ░ ▒░░ ░░   ░ ▒░  ▒ ░▒░ ░  ░   ▒▒   ░   ▒▒     ░
          ░   ▒     ░   ░ ░    ░   ░ ░   ░  ░░ ░  ░   ▒    ░   ▒    ░ ░
              ░           ░          ░   ░  ░  ░      ░        ░


*/
//#include <bits/BaoMinhTranc++.h>
#include <bits/stdc++.h>
#define int int64_t
//#define ll int64_t
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define fi first
#define se second
#define ALL(x) x.begin(),x.end()
#define ALLr(x) x.rbegin(),x.rend()
#define upgrade ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int Max=3e5;
const int N=3e5+3;
const int INF=1e18;
const int MOD=1e9+7;
const int MOD2=1e9+8;
const int base=26;
const int LOG=20;
template<class X,class Y>
    bool minimize(X& x,const Y& y)
    {
        if(x>y){
            x=y;
            return 1;
        }return 0;
    }
template<class X,class Y>
    bool maximize(X& x,const Y& y)
    {
        if(x<y){
            x=y;
            return 1;
        }return 0;
    }
int t[N];
int a[N];
int n,k;
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>t[i];
    int s=t[n]-t[1]+1;
    for(int i=1;i<n;i++)a[i]=t[i+1]-t[i]-1;
    sort(a+1,a+n);
    reverse(a+1,a+n);
    for(int i=1;i<k;i++)s-=a[i];
    cout<<s;
}
void prepare()
{

}
signed main()
{
    upgrade
//    freopen("NKSEX.INP","r",stdin);
//    freopen("NKSEX.OUT","w",stdout);
    prepare();
    int test=1;
//    cin>>test;
    while(test--)solve();
    return 0;
}
/*

                                                                                                       ░▓▓
                                                                 ░▒▒▒         ░▒▒▒▒▒▒░░░               ░▓▓
▓▒        ▒▓▓▓▓▓▓▓▓▓▓▓▓▒                  ░▓▓▓▓▓▓▓▓▓▓▓▒░       ▒▓▓▒      ▒▒▒▒░   ░░░░▒░▒▒▒▒▒▒          ░▓▓    ░░▒▒▒▒▒░░
▒▓▓▒   ▒▓▓░            ░▓▓▒           ░▓▓▓▒            ░▒▓▓░░▓▓▒      ▒▒▒  ▒▒▒▒▒▒░░░▒▒▒▒▒▒▒▒▒▒▒░       ░▓▓▓▒▒▒▒▒▒▒▒▒▒▓▒▒░
   ▓▓▓▓▒                 ░▓▓▒       ▒▓▓▒                 ░▓▓▓░      ░▒░        ░▒▒▒▒▒▒▒▒  ▒▒▒░ ▒▒▒     ░▓▓
                          ░▓▓░     ▓▓▓                                                 ░▒▒▒ ▒▒▒ ░▒▒    ▒▓▒
                           ▒▓▒    ▓▓▓                                      ░░            ▒▒░ ▒▒▒ ▒▒░   ▓▓▓
                           ░▓▒   ░▓▓▓                                  ░▒  ▒▒░           ▒▒░ ▒▒░ ▒▒▒   ▓▓▓░
                           ░▓▒   ░▓▓▓▒                                 ▒▒▒ ░▒▒▒░       ░▒▒░ ░▒▒ ▒▒▒    ▓▓▓▒
                           ▒▓▒     ▓▓▓░                      ░      ▒▒░  ▒▒▒   ▒▒▒▒▒▒▒▒░  ▒▒▒▒▒▒▒▒     ░▓▓▓
                          ░▓▓▒      ▒▓▓▓▒                 ░▓▓▓▓▒     ░▒▒   ░▒▒▒▒▒▒▒▒▒▒▒▒▒▒░ ▒▒▒░        ░▓▓▓
                           ░▒         ░▓▓▓▓▓▓▒░       ▒▓▓▓▓▓▒▓▓▒        ▒▒▒▒▒▒▒░    ░▒▒▒▒▒▒▒░             ▓▓▓▓▒▒       ▒▓▓▓▓
                                           ░░▓▓▓▓▓▓▓▓▒░░     ▒▓▒                 ░▒▒▒▒░                       ░▒▓▓▓▓▓▓▓▓▒░
                                                             ▒▓▓░                  ▒▒░
                            ▓▒                               ▒▓▓░                  ▒▒▒░
                            ▓▓▒                             ░▓▓▒                  ░▒▒▒▒
                             ▓▓▓░                          ▒▓▓▓                    ░▒▒▒
                               ░▓▓▓▓░                   ░▓▓▓▒
                                   ░▓▓▓▓▓▒▒░░░  ░░░▒▒▓▓▓▓░
                                         ░▒▒▒▒▒▒▒▒░
*/

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