Submission #1082851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082851		an22inkle	Stove (JOI18_stove)	C++17	0 / 100	0 ms	348 KiB

stove

#include<bits/stdc++.h>
using pair = std::array<int, 2>;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int N, k;
	std::cin >> N >> k;
	std::vector<int> V(N);
	for (int i = 0; i < N; i++) {
		std::cin >> V[i];
	}

	std::vector<pair> v;
	for (int i = 0; i < N; i++) {
		int j = i + 1;
		while (j < N && V[j] == V[j - 1] + 1) j++;
		v.push_back({V[i] - (V[0] - 1), j - i});
		i = j - 1;
	}

	int n = v.size();
	std::vector<int> parent(n), child(n);
	std::vector<std::array<int, 3>> neigh(n); // 0 head 1 body 2 tail
	std::set<pair> S;
	for (int i = 0; i < n - 1; i++) {
		neigh[i][0] = v[i][1];
		neigh[i][2] = v[i +1][1];
		neigh[i][1] = v[i + 1][0] - v[i][0] - v[i][1];

		parent[i] = i - 1;
		child[i] = i + 1;

		S.insert({neigh[i][0] + neigh[i][1] + neigh[i][2], i});
	}

	int t = n-1;
	while (t > k - 1) {
		pair min = *S.begin(); S.erase(min);
		int i = min[1];
		auto par = neigh[parent[i]], chil = neigh[child[i]];
		

		if (parent[i] >= 0) {
			S.erase({par[0]+par[1]+par[2], parent[i]});	
			neigh[parent[i]][2] = min[0];
			child[parent[i]] = child[i];

			auto x = neigh[parent[i]];
			S.insert({x[0] + x[1] + x[2], parent[i]});
		}

		if (child[i] < n) {
			S.erase({chil[0]+chil[1]+chil[2], child[i]});
			neigh[child[i]][0] = min[0];
			parent[child[i]] = parent[i];

			auto x = neigh[child[i]];
			S.insert({x[0] + x[1] + x[2], child[i]});
		}
		t--;
	}

	if (n == 1) {
		std::cout << v[0][1] << '\n';
		return 0;
	}

	std::set<int> T;
	for (auto u : S) {
		T.insert(u[1]);
	}

	int ans = 0;
	for (auto u : T) {
		ans += neigh[u][0];
	} ans += neigh[*(T.rbegin())][2];
	std::cout << ans << '\n';
}

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