Submission #142589

#	Time	Username	Problem	Language	Result	Execution time	Memory
142589		ahmet	Stove (JOI18_stove)	C++14	100 / 100	31 ms	2808 KiB

stove

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(long long (i)=0;(i)<(n);++(i))
//REF TE KUCUK ESITTIR YOK DIKKKKKKKKKKKKATTTTTT
#define ref(i,a,b) for (long long (i)=(a); (i)<(b); ++(i))
#define INF 0xFFFFFF
#define endl '\n'
#define pb push_back
#define mp make_pair
const unsigned int mod = 1e9+7;
const int mx=1e5+5;
int n,k;//ll or int ?
ll ans=1e17;
ll a[mx];
ll sub[mx-1];
/*void solve(ll v,ll kk,ll bitti,ll top){
	if(v==(n-1) and kk==(k-1)){
	//	if(bitti)
			ans=min(ans,top+1);
	//	else return;
	}
	else if(v==(n-1) and kk==k){
		if(!bitti)
			ans=min(ans,top);
		else return;
	}
	if(v==(n-1))return;
	if(kk>k)return;
	if(bitti){
		solve(v+1,kk+1,bitti,top+1);
		solve(v+1,kk,1-bitti,top+sub[v]+1);
	}
	else{
		solve(v+1,kk,bitti,top+sub[v]);//dikkat
		solve(v+1,kk+1,1-bitti,top+1);
	}

	return;
}*/
int main(){
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout); 
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin >> n >> k;
	rep(i,n)cin >> a[i];
	ll ans=n;
	int cc=0;
	vector <int> wait;
	ref(i,1,n){
		if(!(a[i]==(a[i-1]+1))){
			wait.pb(a[i]-a[i-1]-1);
			++cc;
		}
	}
	++cc;
	sort(wait.begin(),wait.end());
	for(int i=0;i<max(0,cc-k);++i)ans+=wait[i];
	cout << ans << endl;
}
	

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