Submission #792880

#	Time	Username	Problem	Language	Result	Execution time	Memory
792880		IvanJ	Fireworks (APIO16_fireworks)	C++17	26 / 100	24 ms	1108 KiB

fireworks

#include<bits/stdc++.h>

#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 305;

int n, m;
int dp[maxn][maxn];
vector<ii> adj[maxn];

int rek(int x, int len) {
	if(dp[x][len] != -1)
		return dp[x][len];
	if(adj[x].size() == 0)
		return dp[x][len] = (len == 0) ? 0 : 1e9;
	
	int ret = 0;
	for(auto p : adj[x]) {
		int reti = 1e9;
		for(int i = 0;i <= len;i++) {
			int l = len - i;
			reti = min(reti, rek(p.x, i) + abs(p.y - l));
		}
		ret += reti;
	}
	return dp[x][len] = ret;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1;i < n + m;i++) {
		int p, c;
		scanf("%d%d", &p, &c);
		p--;
		adj[p].pb({i, c});
	}
	if(n == 1) {
		vector<int> v;
		for(auto p : adj[0]) v.pb(p.y);
		sort(all(v));
		int med = v[m / 2];
		ll ans = 0;
		for(int i : v) ans += (ll)abs(i - med);
		printf("%lld\n", ans);
		return 0;
	}
	
	memset(dp, -1, sizeof dp);
	int ans = 1e9;
	for(int i = 0;i < maxn;i++) 
		ans = min(ans, rek(0, i));
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &p, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~

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