Submission #849676

#	Time	Username	Problem	Language	Result	Execution time	Memory
849676		chilengaming	Stove (JOI18_stove)	C++17	100 / 100	15 ms	2420 KiB

stove

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

//Num
#define int long long 
#define ld long double

//Vector or String
#define all(v) v.begin(), v.end()
#define sor(v) sort(all(v))
#define sz(v) (long long) v.size()
#define remu(v) v.erase(unique(all(v)), end(v))
#define pb push_back
#define eb emplace_back

//Pair Map
#define fi first 
#define se second
#define pii pair<int, int>
#define mii map<int, int>
#define mib map<int, bool>

//Loop
#define fou(i, a, b) for(int i = a; i <= b; i++)
#define fod(i, a, b) for(int i = a; i >= b; i--)

//Gragh
const int dx[8] = {0, 0, 1, -1, -1, -1, 1, 1};
const int dy[8] = {1, -1, 0, 0, -1, 1, -1, 1};

//Some Func
template <class T> bool ckmin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}
template <class T> bool ckmax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}
string its(int n) {
    stringstream ss;
    ss << n;
    string s;
    ss >> s;
    return s;
}
int sti(string s) {
    stringstream ss;
    ss << s;
    int n;
    ss >> n;
    return n;
}

//Input Output 
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define TASK "fi"
#define el '\n'

//Mod MaxN 
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 1;
const int INF = 1e18;
const ld PI = acos((ld)-1);
int ar[100001];

void solve() {
    int n, k;
    cin >> n >> k;
    fou(i, 1,n ) {
        cin >> ar[i];
    }
    int ans = ar[n] - ar[1] + 1;
    vector<int> v;
    fou(i, 2, n) {
        v.pb(ar[i] - ar[i - 1] - 1);
    }
    sort(v.begin(), v.end(), greater<int>());
    fou(i ,0, k-2) {
        ans -= v[i];
    }
    cout << ans;
}

signed main() {
    FIO;
    //freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
    int Q = 1;
    //cin >> Q;
    while(Q--) {
        solve();
    }
}

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