oj.uz

Submission #69314

# Submission time Handle Problem Language Result Execution time Memory
69314 2018-08-20T12:15:31 Z FedericoS Fireworks (APIO16_fireworks) C++14
0 / 100
 6 ms 484 KB 
#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pll;

ll x,y;
ll INF=1e18;
ll N,M,K=600;
ll DP[305][500];
vector<pll> grafo[305];
ll ans;

void DFS(ll k, ll p){

	if(k>N){
		for(int i=1;i<K;i++)
			DP[k][i]=INF;
		return;
	}

	for(pll f:grafo[k])
		if(f.first!=p)
			DFS(f.first,k);

	for(int i=0;i<K;i++)
		for(pll f:grafo[k])
			if(f.first!=p){
				ll res=INF;
				for(int j=0;j<=i;j++)
					res=min(res,DP[f.first][j]+abs(f.second-(i-j)));
				DP[k][i]+=res;
			}

}

int main(){

	cin>>N>>M;
	for(int i=2;i<=N+M;i++){
		cin>>x>>y;
		grafo[i].push_back({x,y});
		grafo[x].push_back({i,y});
	}

	DFS(1,0);

	ans=INF;
	for(int i=0;i<K;i++)
		ans=min(ans,DP[1][i]);
	cout<<ans;

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 19.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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