Submission #672264

#	Time	Username	Problem	Language	Result	Execution time	Memory
672264		Dan4Life	Fireworks (APIO16_fireworks)	C++17	26 / 100	22 ms	1620 KiB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
#define fi first
#define se second
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
const int maxn = 5e3+10;
const int LINF = (int)1e18;
int p[maxn], c[maxn];
int n, m, ans;
vector<pair<int,int>> adj[maxn];
int dp[maxn][310];
bool ok[maxn][310];

void dfs(int s, int p){
	if(s>n){ dp[s][0]=0;ok[s][0]=1; return; }
	for(auto cur : adj[s]){
		int u = cur.fi, c = cur.se;
		if(u==p) continue; dfs(u,s);
		for(int i = 0; i <= 300; i++){
			int price = LINF;
			for(int j = 0; j <= i; j++)
				if(ok[u][j]) price = min(price, abs(c-(i-j))+dp[u][j]);
			if(price==LINF) ok[s][i]=false;
			else dp[s][i]+=price;
		}
	}
}

int32_t main() {
	cin >> n >> m; ans=LINF;
	for(int i = 2; i <= n+m; i++){
		cin >> p[i] >> c[i];
		adj[i].pb({p[i],c[i]});
		adj[p[i]].pb({i,c[i]});
	}
	if(n==1){ ans=0; vector<int> v;
		for(int i = n+1; i <= n+m; i++) v.pb(c[i]);
		sort(all(v));  int ans = 0;
		for(auto u : v) ans+=abs(u-v[sz(v)/2]);
		cout << ans; return 0;
	}
	for(int i = 1; i <= n; i++)
		for(int j = 0; j <= 300; j++)
			ok[i][j]=1;
	dfs(1,1);
	for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
}

Compilation message (stderr)

fireworks.cpp: In function 'void dfs(long long int, long long int)':
fireworks.cpp:22:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   22 |   if(u==p) continue; dfs(u,s);
      |   ^~
fireworks.cpp:22:22: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   22 |   if(u==p) continue; dfs(u,s);
      |                      ^~~
fireworks.cpp: In function 'int32_t main()':
fireworks.cpp:50:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   50 |  for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
      |  ^~~
fireworks.cpp:50:69: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   50 |  for(int i = 0; i <= 300; i++) if(ok[1][i]) ans=min(ans, dp[1][i]); cout << ans;
      |                                                                     ^~~~

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