oj.uz

답안 #69315

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69315 2018-08-20T12:16:55 Z FedericoS Fireworks (APIO16_fireworks) C++14
19 / 100
 148 ms 2444 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][700];
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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 616 KB Output is correct
2 Correct 17 ms 672 KB Output is correct
3 Correct 34 ms 852 KB Output is correct
4 Correct 30 ms 1168 KB Output is correct
5 Correct 34 ms 1260 KB Output is correct
6 Correct 39 ms 1504 KB Output is correct
7 Correct 53 ms 1620 KB Output is correct
8 Correct 44 ms 1780 KB Output is correct
9 Correct 72 ms 1780 KB Output is correct
10 Correct 58 ms 1848 KB Output is correct
11 Correct 59 ms 2032 KB Output is correct
12 Correct 71 ms 2164 KB Output is correct
13 Correct 76 ms 2176 KB Output is correct
14 Correct 83 ms 2300 KB Output is correct
15 Correct 81 ms 2432 KB Output is correct
16 Correct 88 ms 2432 KB Output is correct
17 Correct 80 ms 2440 KB Output is correct
18 Correct 117 ms 2444 KB Output is correct
19 Correct 148 ms 2444 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -