Submission #868259

#	Time	Username	Problem	Language	Result	Execution time	Memory
868259		TheLostSun	Stove (JOI18_stove)	C++14	100 / 100	17 ms	2376 KiB

stove

/*
   _____       __                       ___    __   _            
  / ___/____  / /________ _            /   |  / /__(_)___  ____ _
  \__ \/ __ \/ / ___/ __ `/  ______   / /| | / //_/ / __ \/ __ `/
 ___/ / /_/ / / /  / /_/ /  /_____/  / ___ |/ ,< / / / / / /_/ / 
/____/\____/_/_/   \__,_/           /_/  |_/_/|_/_/_/ /_/\__,_/  
                                                                 
*/

#include <bits/stdc++.h>

using namespace std;

int n,k;
int a[100001];
vector<int> ve;

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int res = a[n] - a[1] + 1;
	int tru = 0;
	for (int i = 1; i <= n - 1; i++) ve.push_back(a[i + 1] - (a[i] + 1));
	sort(ve.begin(), ve.end());
	k--;
	for (int i = ve.size() - 1; i >= 0; i--)
	{
		if (k == 0) break;
		k--;
		tru += ve[i];
	};
	cerr << res << " " << tru << '\n';
	cout << res - tru;
}

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