oj.uz

Submission #1092666

# Submission time Handle Problem Language Result Execution time Memory
1092666 2024-09-24T17:45:45 Z alexander707070 Fireworks (APIO16_fireworks) C++14
19 / 100
 52 ms 15036 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14428 KB Output is correct
2 Correct 13 ms 14428 KB Output is correct
3 Correct 13 ms 14608 KB Output is correct
4 Correct 19 ms 14680 KB Output is correct
5 Correct 21 ms 14428 KB Output is correct
6 Correct 23 ms 14424 KB Output is correct
7 Correct 26 ms 14428 KB Output is correct
8 Correct 30 ms 14684 KB Output is correct
9 Correct 31 ms 14712 KB Output is correct
10 Correct 37 ms 14684 KB Output is correct
11 Correct 39 ms 14680 KB Output is correct
12 Correct 39 ms 14684 KB Output is correct
13 Correct 42 ms 14696 KB Output is correct
14 Correct 52 ms 15036 KB Output is correct
15 Correct 45 ms 14684 KB Output is correct
16 Correct 50 ms 14680 KB Output is correct
17 Correct 46 ms 14680 KB Output is correct
18 Correct 45 ms 14684 KB Output is correct
19 Correct 44 ms 14684 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 14424 KB Output isn't correct
2 Halted 0 ms 0 KB -