Submission #871149

#	Time	Username	Problem	Language	Result	Execution time	Memory
871149		aaron_dcoder	Stove (JOI18_stove)	C++17	100 / 100	16 ms	3132 KiB

stove

#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;


int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	ll N,K;
	cin >> N >> K;

	vector<ll> T(N);

	for (ll i = 0; i < N; ++i)
	{
	 	cin >> T[i];
	}


	vector<ll> segs(N-1);
	for (ll i = 0; i < N-1; ++i)
	{
		segs[i] = T[i+1]-T[i] -1;
	}
	sort(segs.begin(),segs.end());
	K--;

	ll savings=0;

	while (!segs.empty() && K>0) {
		savings += *segs.crbegin();
		segs.pop_back();
		K--;
	}
	dbgv(savings);

	cout << T[N-1]-T[0]+1 - savings;



}

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