Submission #256973

#	Time	Username	Problem	Language	Result	Execution time	Memory
256973		lani1akea	Stove (JOI18_stove)	C++17	100 / 100	52 ms	3192 KiB

stove

#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define pb push_back
#define endl '\n'

using namespace std;

const int MOD = 1e9 + 7;
const int N = 1e5 + 10;

int t[N];

bool e(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b) {
	return (a.S.F < b.S.S);
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<pair<int, pair<int, int>>> v;
	for (int i = 0; i < n; ++i) {
		cin >> t[i];
		if (i) v.pb({t[i] - t[i - 1], { i-1, i}});
	}
	sort(v.rbegin(), v.rend());
	v.erase(v.begin() + k - 1, v.begin() + (v.size()));
	sort(v.begin(), v.end(), e);
	ll sum = 0;
	int l = 0;
	for ( auto i: v) {
		//cout << i.S.F << " " << i.S.S << endl;
		sum += (t[i.S.F] - t[l] + 1) * 1LL;
		l = i.S.S;
	}
	sum += (t[n-1] - t[l] + 1) * 1LL;
	cout << sum << endl;
}

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