Submission #260337

#	Time	Username	Problem	Language	Result	Execution time	Memory
260337		terencehill	Stove (JOI18_stove)	C++14	100 / 100	30 ms	2844 KiB

stove

#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;
}

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