Submission #776440

#	Time	Username	Problem	Language	Result	Execution time	Memory
776440		Hacv16	Election Campaign (JOI15_election_campaign)	C++17	10 / 100	65 ms	49908 KiB

election_campaign

#include <bits/stdc++.h>
using namespace std;
 
const int LOG = 21;
const int MAX = 2e6 + 15;
 
int n, m, dp[MAX];
vector<pair<int, int>> queries[MAX];
 
int32_t main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	cin >> n;
 
	for(int i = 1; i < n; i++){
		int u, v; cin >> u >> v;
	}
	
	cin >> m;
 
	while(m--){
		int u, v, w; cin >> u >> v >> w;
		if(u > v) swap(u, v);
		queries[v].emplace_back(u, w);
	}	

	for(int i = 1; i <= n; i++){
		dp[i] = dp[i - 1];

		for(auto [j, w] : queries[i])
			dp[i] = max(dp[i], dp[j - 1] + w);
	}

	cout << dp[n] << '\n';	
}

• Subtask 1: 0 / 10
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 30
• Subtask 5: 0 / 10
• Subtask 6: 0 / 40