Submission #954840

#	Time	Username	Problem	Language	Result	Execution time	Memory
954840		Itamar	Fireworks (APIO16_fireworks)	C++14	19 / 100	18 ms	1152 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;
	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: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45