Submission #1033665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033665		vjudge1	Stove (JOI18_stove)	C++17	100 / 100	16 ms	2524 KiB

stove

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll  i=(a);i<=(b);i++)
#define Ford(i,a,b) for(ll  i=(a);i>=(b);i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define endl "\n"
using namespace std;
int Dx[] = {0, 1, 0, -1, -1, -1, 1, 1};
int Dy[] = {-1, 0, 1, 0, 1, -1, 1, -1};
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
const ll inf = 1000000000000000000;
const int N = 1000;
const int block_size = 300;
const ll MOD =  1e9 + 7; /* 998244353 */
const int LG = 18;
const int K = 20;	
const int M = 1000000;
ll nph(ll k, ll x) { return ((x >> k) & 1); }

void Solve() { 
	ll n,k; cin>>n>>k; ll a[n+3];
	For(i, 1, n) cin>>a[i];
	vector<ll> v;
	For(i, 2, n) {
		v.pb(a[i] - a[i-1] - 1);
	}
	sort(v.rbegin(), v.rend());
	ll ans = a[n] + 1 - a[1];
	for(ll i = 0; i < min(k-1, (ll)v.size()); i++) ans -= v[i];
	cout << ans;
}	
int main() {
    // freopen("BETTER.INP", "r", stdin);
    // freopen("BETTER.OUT", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin>>t; 
    while(t--) 
    	Solve();
}
 

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