Submission #636837

#	Time	Username	Problem	Language	Result	Execution time	Memory
636837		lovrot	Fireworks (APIO16_fireworks)	C++11	0 / 100	2075 ms	980 KiB

fireworks

#include <bits/stdc++.h>

#define ll long long
#define X first
#define Y second
#define pii pair<int, int> 
#define pb push_back 

using namespace std; 

const int N = 310;
const ll INF = 1e9;

ll abs2(ll x){ 
	return x < 0 ? -x : x;
}

int n, m;
ll dp[N][N], c[N], p[N], calc[N];
ll maxi, dist;

vector<ll> v;
vector<int> g[N];

ll DP(int u, ll d){ 
	if(g[u].size() == 0){
		if(d > dist) return INF;
		return abs2(dist - (d + c[u]));
	}
	if(dp[u][d] != -1) return dp[u][d];
	dp[u][d] = INF;
	for(ll dx = 0; dx + d <= dist; dx++){ 
		ll res = abs2(c[u] - dx);
		for(int v : g[u]){ 
			res += DP(v, d + dx);		
		}
		dp[u][d] = min(dp[u][d], res);
	}
	return dp[u][d];
}

int main(){
	ios_base::sync_with_stdio(false);

	scanf("%d%d", &n, &m);

	for(int i = 2; i <= n + m; i++){ 
		scanf("%d%d", &p[i], &c[i]);
		g[p[i]].pb(i);
		calc[i] = calc[p[i]] + c[i];
		if(i > n) v.pb(calc[i]);
	}

	sort(v.begin(), v.end());

	if(v.size() == 1){ 
		printf("0\n");
	} else {
		dist = v[v.size() / 2];
		memset(dp, -1, sizeof(dp));
		ll ans = DP(1, 0);
		dist = v[(v.size() - 1)/ 2];
		memset(dp, -1, sizeof(dp));
		ans = min(ans, DP(1, 0));
		printf("%d", ans);
	}
	return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int main()':
fireworks.cpp:48:11: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |          ~^     ~~~~~
      |           |     |
      |           int*  long long int*
      |          %lld
fireworks.cpp:48:13: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |            ~^          ~~~~~
      |             |          |
      |             int*       long long int*
      |            %lld
fireworks.cpp:65:12: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   65 |   printf("%d", ans);
      |           ~^   ~~~
      |            |   |
      |            int long long int
      |           %lld
fireworks.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
fireworks.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d%d", &p[i], &c[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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