Submission #202380

#	Time	Username	Problem	Language	Result	Execution time	Memory
202380		cgiosy	Fireworks (APIO16_fireworks)	C++17	100 / 100	263 ms	60536 KiB

fireworks

#include <bits/stdc++.h>
#define rep(i,x,n) for(decltype(n) i=x; i<n; i++)
using namespace std;
using pq=priority_queue<long>;

int main() {
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	int N, M; long r=0;
	cin>>N>>M;
	vector<int> W(N+M);
	vector<vector<int>> G(N);
	rep(i, 1, N+M) {
		int j;
		cin>>j>>W[i];
		G[j-1].push_back(i);
		r+=W[i];
	}
	function<pq(int)> f=[&](int i) {
		pq q;
		if(i<N) {
			for(int j:G[i]) {
				pq p=f(j);
				if(q.size()<p.size()) swap(q, p);
				while(p.size()) q.push(p.top()), p.pop();
			}
			rep(j, 1, G[i].size()) q.pop();
			long x=q.top()+W[i]; q.pop();
			long y=q.top()+W[i]; q.pop();
			q.push(x), q.push(y);
		} else q.push(W[i]), q.push(W[i]);
		return q;
	};
	auto q=f(0);
	long p=q.top(), k=0; q.pop();
	while(q.size())
		r-=k++*(p-q.top()), p=q.top(), q.pop();
	cout<<r-k*p;
}

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45