Submission #799933

#	Time	Username	Problem	Language	Result	Execution time	Memory
799933		OAleksa	Stove (JOI18_stove)	C++14	100 / 100	28 ms	3124 KiB

stove

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

int main()
{
	  ios_base::sync_with_stdio(false);
	  cin.tie(0);
	  cout.tie(0);
	  int tt = 1;
		//cin >> tt;
	  while(tt--) {
			int n, k;
			cin >> n >> k;
			vector<int> a(n);
			for(int i = 0;i < n;i++)
				cin >> a[i];
			vector<pair<int, int>> p(n);
			for(int i = 1;i < n;i++)
				p[i] = {a[i] - a[i - 1], i - 1};
			sort(p.begin(), p.end(), greater<pair<int, int>>());
			vector<int> g;
			for(int i = 0;i < k - 1;i++)
				g.push_back(p[i].s);
			sort(g.begin(), g.end());
			int ans = 0;
			int ptr = a[0];
			for(auto x : g) {
				ans += a[x] + 1 - ptr;
				ptr = a[x + 1];
			}
			ans += a[n - 1] + 1 - ptr;
			cout << ans;
		}
    return 0;
}

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