Submission #1092666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092666		alexander707070	Fireworks (APIO16_fireworks)	C++14	19 / 100	52 ms	15036 KiB

fireworks

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

const long long inf=1e17;

int n,m;
int p[MAXN],c[MAXN];
vector< pair<int,int> > v[MAXN],g[MAXN];
vector<long long> dists;

int ans;
int dp[307][307];
bool li[307][307];

int solve(int x,int len){
	if(len<0)return 1e9;
	
	if(v[x].empty()){
		if(len==0)return 0;
		else return 1e9;
	}

	if(li[x][len])return dp[x][len];
	li[x][len]=true;

	for(int i=0;i<v[x].size();i++){
		int mins=1e9;

		for(int f=0;f<=300;f++){
			mins=min(mins,abs(f-v[x][i].second)+solve(v[x][i].first,len-f));
		}

		dp[x][len]+=mins;
	}

	return dp[x][len];
}

int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	n+=m;
	for(int i=2;i<=n;i++){
		cin>>p[i]>>c[i];

		v[p[i]].push_back({i,c[i]});
		g[p[i]].push_back({i,c[i]});
	}

	ans=1e9;
	for(long long len=0;len<=300;len++){
		ans=min(ans,solve(1,len));
	}

	cout<<ans<<"\n";

    return 0;
}

Compilation message (stderr)

fireworks.cpp: In function 'int solve(int, int)':
fireworks.cpp:27:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int i=0;i<v[x].size();i++){
      |              ~^~~~~~~~~~~~

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