Submission #411661

#	Time	Username	Problem	Language	Result	Execution time	Memory
411661		nichke	Stove (JOI18_stove)	C++14	100 / 100	31 ms	6288 KiB

stove

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

int n, k;
vector<int> diff;
vector<pair<int, int>> a;
vector<pair<int, int>> b;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++) {
		int l, r; cin >> l; r = l + 1;
		a.push_back({l, r});
	}
	sort(a.begin(), a.end());
	int l = a[0].first, r = a[0].second;
	for (int i = 1; i < a.size(); i++) {
		if (a[i].first <= a[i - 1].second) {
			r = max(a[i].second, r);
		} else {
			b.push_back({l, r});
			l = a[i].first;
			r = a[i].second;
		}
	}
	b.push_back({l, r});
	for (int i = 1; i < b.size(); i++) {
		diff.push_back(b[i].first - b[i - 1].second);
	}
	sort(diff.begin(), diff.end());
	int cnt = 0;
	int res = 0;
	for (int i = 0; i < b.size(); i++) {
		res += b[i].second - b[i].first;
		cnt++;
	}
	int j = 0;
	while (cnt > k) {
		cnt--;
		res += diff[j++];
	}
	cout << res << '\n';
	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:22:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 1; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
stove.cpp:32:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 1; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~
stove.cpp:38:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  for (int i = 0; i < b.size(); i++) {
      |                  ~~^~~~~~~~~~

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