Submission #1293808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293808		loiloiloi	Stove (JOI18_stove)	C++20	100 / 100	17 ms	1484 KiB

stove

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define pii pair<int,int>
const int base = 79;
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int maxN = 1e5 + 6;
using namespace std;
int n, k, t[maxN];


int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> t[i];

	vector<int> intervals;
	for (int i = 2; i <= n; i++) intervals.pb(t[i] - t[i - 1] - 1);
	sort(all(intervals), greater<int>());

	int ans = t[n] - t[1] + 1;
	for (int i = 0; i < k - 1; i++) {
        ans -= intervals[i];
	}
	cout << ans << '\n';


	return 0;
}

// special cases (n=1?)
// 2 segments intersect: max(l, L) <= min(r, R)

/*
-Use: ordered_set st;
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
(greater / less_equal)
-Use: loang
int X[4] = {0, -1, 1, 0};
int Y[4] = {1, 0, 0, -1};
*/

/*
#######################################
##                                   ##
##             LuOsIer               ##
##                                   ##
#######################################
*/

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