Submission #781537

#	Time	Username	Problem	Language	Result	Execution time	Memory
781537		acatmeowmeow	Stove (JOI18_stove)	C++11	100 / 100	27 ms	7392 KiB

stove

#include <bits/stdc++.h>

using namespace std;

#define int long long 

int find(int x, vector<int>&par) { return x == par[x] ? x : find(par[x], par); }

bool same(int x, int y, vector<int>&par) { return find(x, par) == find(y, par); }

void unite(int x, int y, vector<int>&sz, vector<int>&par) {
	x = find(x, par), y = find(y, par);
	if (sz[x] < sz[y]) swap(x, y);
	sz[x] += sz[y], par[y] = x;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, k;
	cin >> n >> k;
	vector<int> arr(n + 5);
	for (int i = 1; i <= n; i++) cin >> arr[i];
	vector<int> sz(n + 5), par(n + 5), mn(n + 5, 1e18), mx(n + 5, -1e18);
	for (int i = 1; i <= n; i++) par[i] = i, sz[i] = 1;
	vector<pair<int, int>> edge;
	for (int i = 2; i <= n; i++) edge.push_back({arr[i] - arr[i - 1], i});
	sort(edge.begin(), edge.end());
	int cc = n;
	for (int i = 0; i < edge.size() && cc > k; i++) {
		int index = edge[i].second;
		if (!same(index, index - 1, par)) unite(index, index - 1, sz, par), cc--;
	}
	for (int i = 1; i <= n; i++) {
		mn[find(i, par)] = min(mn[find(i, par)], arr[i]);
		mx[find(i, par)] = max(mx[find(i, par)], arr[i]);
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (find(i, par) == i) {
			ans += mx[i] - mn[i] + 1;
		}
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

stove.cpp: In function 'int main()':
stove.cpp:31: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]
   31 |  for (int i = 0; i < edge.size() && cc > k; i++) {
      |                  ~~^~~~~~~~~~~~~

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