Submission #389084

#	Time	Username	Problem	Language	Result	Execution time	Memory
389084		prvocislo	Fireworks (APIO16_fireworks)	C++17	26 / 100	2082 ms	720 KiB

fireworks

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
typedef long long ll;
using namespace std;

const int maxi = 307, inf = 1e9 + 79;
vector<vector<int> > dp(maxi, vector<int>(maxi, inf));
vector<vector<pair<int, int> > > g(maxi);
int n, m;
int rek(int u, int dist, int c)
{
	if (u >= n) return abs(c - dist);
	if (dp[u][dist] != inf) return dp[u][dist];
	for (int cl = 0; cl <= dist; cl++)
	{
		int sum = abs(cl - c);
		for (pair<int, int> v : g[u])
			sum += rek(v.first, dist - cl, v.second);
		dp[u][dist] = min(dp[u][dist], sum);
		if (!c) break;
	}
	return dp[u][dist];
}
void subtask1()
{
	vector<int> v;
	for (int i = 1, p, c; i < n + m; i++)
	{
		cin >> p >> c;
		v.push_back(c);
	}
	sort(v.begin(), v.end());
	ll ans = 0;
	for (int i = 0; i < v.size(); i++) ans += abs(v[i] - v[(v.size() / 2)]);
	cout << ans << "\n";
	exit(0);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	if (n == 1) subtask1();
	for (int i = 1, p, c; i < n + m; i++)
	{
		cin >> p >> c;
		g[--p].push_back({ i, c });
	}
	int ans = inf;
	for (int dist = 0; dist < maxi; dist++)
		ans = min(ans, rek(0, dist, 0));
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'void subtask1()':
fireworks.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < v.size(); i++) ans += abs(v[i] - v[(v.size() / 2)]);
      |                  ~~^~~~~~~~~~

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