Submission #954844

#	Time	Username	Problem	Language	Result	Execution time	Memory
954844		Itamar	Fireworks (APIO16_fireworks)	C++14	26 / 100	18 ms	1128 KiB

fireworks

#include <iostream>
using namespace std;
#include <vector>
#define vi vector<int>
#define ll long long
#include <algorithm>
#include <set>
#include <string>
#include <bitset>
#include <cmath>
#include <math.h>
#define pll pair<ll,ll>
#define vll vector<ll>
#define pi pair<int,int>
#include <map>
#include <queue>
#define x first
#define y second
#define pd pair<double,double>

const int siz = 301;
int pad[siz];
int w[siz];
vi son[siz];
ll dp[siz][siz];
int main()
{
	int n, m;
	cin >> n >> m;
	if (n == 1) {
		vi v;
		for (int i = 1; i < n + m; i++) {
			int p, c;
			cin >> p >> c;
			p--;
			v.push_back(c);
		}
		sort(v.begin(), v.end());
		ll ans = 0;
		for (int i = 0; i < m; i++) {
			ans += abs(v[m / 2] - v[i]);
		}
		cout << ans;
	}
	else {
		for (int i = 1; i < n + m; i++) {
			int p, c;
			cin >> p >> c;
			p--;
			pad[i] = p, w[i] = c;
			son[p].push_back(i);
		}
		for (int i = n + m - 1; i >= 0; i--) {
			for (int j = 0; j < siz; j++) {
				if (i >= n && j > 0)dp[i][j] = 1e9;
			}
		}
		for (int i = n - 1; i >= 0; i--) {
			for (int j = 0; j < siz; j++) {
				for (int s : son[i]) {
					int pl = 1e9;
					for (int k = 0; k <= j; k++) {
						pl = min((ll)pl, abs(w[s] - k) + dp[s][j - k]);
					}
					dp[i][j] += pl;
				}
			}
		}
		ll ans = 1e9;
		for (int i = 0; i < siz; i++)ans = min(ans, dp[0][i]);
		cout << ans;
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file

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