Submission #260337

#TimeUsernameProblemLanguageResultExecution timeMemory
260337terencehillStove (JOI18_stove)C++14
100 / 100
30 ms2844 KiB
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

void solve() {
	int n, k;
	cin >> n >> k;
	
	vi t(n);
	for(int i = 0; i < n; i++) cin >> t[i];

	vii dif;
	for(int i = 1; i < n; i++) dif.emplace_back(t[i] - t[i - 1], i - 1);
	
	sort(all(dif));
	reverse(all(dif));
	
	int ans = 0;
	for(int i = 0; i < k - 1; i++) {
		ans += t[dif[i].ss + 1] - t[dif[i].ss] - 1; 	
	}
	
	cout << t.back() - t[0] - ans + 1 << endl;
}

int main(){
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...