Submission #207176

#	Time	Username	Problem	Language	Result	Execution time	Memory
207176		cstuart	Stove (JOI18_stove)	C++17	100 / 100	19 ms	2292 KiB

stove

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#define MOD 1000000007ll
#define EPS 1e-9

typedef long long         ll;
typedef long double       ld;
typedef pair <ll,ll>      pl;
typedef tuple <ll,ll,ll>  tl;

ll N, K, T[100005], A;
vector <ll> gaps;

inline void read(ll& v) {
	v = 0;
	char ch = getchar_unlocked();
	while (ch < '0' || ch > '9')
	    ch = getchar_unlocked();
	while (ch >= '0' && ch <= '9') {
		v = (v << 3) + (v << 1) + ch - '0';
		ch = getchar_unlocked();
	}
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	read(N);
	read(K);
	K = min(N, K);
	for (ll i = 1; i <= N; i++) read(T[i]);
	A = T[N] - T[1] + 1;
	
	for (ll i = 2; i <= N; i++) gaps.push_back(T[i] - T[i-1] - 1);
	sort(gaps.begin(), gaps.end(), greater<ll>());
	
	for (ll i = 0; i < K-1; i++) A -= gaps[i];
	cout << A;
	
    return 0;
}

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