Submission #1258059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258059		utku	Stove (JOI18_stove)	C++20	100 / 100	14 ms	1476 KiB

stove

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef multiset<int> mi;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int,int>>> vvpii;
typedef set<int> si;

const int INF = 1e9 + 7;         
const ll LINF = 1e18 + 7;        
const ll MOD = 1e9;         
const double EPS = 1e-9;         
const double PI = acos(-1.0);    

#define fastio ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define F first
#define S second

int t; 

inline void solve() {
    int N, K;
    cin >> N >> K;
    vi g;

    if(K >= N) {cout << N << '\n'; return;}
    for(int i = 0;i<N;i++){
        int t1; cin >> t1;
        g.pb(t1);
    }
    sort(all(g));
    
    vi v;
    for(int i = 0; i+1 < N; ++i) {
        long long gap = g[i+1] - (g[i] + 1);
        v.push_back(gap);                
    }
    sort(all(v));
    int merges = N-K;

    ll extra = 0;

    for(int i = 0;i<merges;i++){ extra += v[i];}

    cout << (ll)N+extra;

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    t = 1;
    while(t--) solve();
    return 0;
}

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