Submission #1189718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189718		nouka28	Stove (JOI18_stove)	C++20	100 / 100	14 ms	3792 KiB

stove

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

// #include<atcoder/all>
// using namespace atcoder;
// using mint=atcoder::modint998244353;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define rng(i,l,r) for(int i=(l);i<(r);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrng(i,l,r) for(int i=(r)-1;i>=(l);i--)

#define fi first
#define se second
#define all(x) (x).begin(),(x).end()

struct fast_io{fast_io(){cin.tie(nullptr)->sync_with_stdio(false);}}_;

signed main(){
	int N,K;cin>>N>>K;
	vector<pair<int,int>> v;
	rep(i,N){
		int t;cin>>t;
		if(v.size()&&v.back().se==t)v.back().se++;
		else v.push_back({t,t+1});
	}

	vector<int> d;
	rep(i,v.size()-1){
		d.push_back(v[i+1].fi-v[i].se);
	}
	sort(all(d));
	int ans=0;
	rep(i,v.size())ans+=v[i].se-v[i].fi;
	rep(i,max<int>(0,v.size()-K))ans+=d[i];
	cout<<ans<<endl;
}

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