oj.uz

답안 #411686

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411686 2021-05-25T18:04:24 Z soroush Fireworks (APIO16_fireworks) C++17
19 / 100
 22 ms 688 KB 
//叫んで 藻掻もがいて 瞼まぶたを腫らしても
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll , ll> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 300 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n , m;
vector < pii > adj[maxn];
int dp[maxn][maxn];

int solve(int v){
	if(adj[v].size() == 0){
		for(int i = 0 ; i < maxn ; i ++)dp[v][i] = 1e6;
		dp[v][0] = 0;
		return 0;
	}
	for(auto u : adj[v])
		solve(u.first);
	for(int i = 0 ; i < maxn ; i ++){
		for(auto uw : adj[v]){
			int u = uw.first , w = uw.second;
			int mn = 1e6;
			for(int j = 0 ; j <= i ; j ++)
				mn = min(mn , abs(w - j) + dp[u][i - j]);
			dp[v][i] += mn;
		}
	}
	
	return *min_element(dp[v] , dp[v] + maxn);
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	n += m;
	for(int i = 2 ; i <= n ; i ++){
		int v , w;
		cin >> v >> w;
		adj[v].pb({i , w});
	}
	cout << solve(1);
	return(0);
}

Subtask #1
0 / 7.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 5 ms 332 KB Output is correct
4 Correct 7 ms 332 KB Output is correct
5 Correct 8 ms 480 KB Output is correct
6 Correct 9 ms 460 KB Output is correct
7 Correct 10 ms 460 KB Output is correct
8 Correct 12 ms 552 KB Output is correct
9 Correct 12 ms 460 KB Output is correct
10 Correct 14 ms 588 KB Output is correct
11 Correct 15 ms 624 KB Output is correct
12 Correct 17 ms 528 KB Output is correct
13 Correct 20 ms 660 KB Output is correct
14 Correct 19 ms 660 KB Output is correct
15 Correct 21 ms 688 KB Output is correct
16 Correct 19 ms 584 KB Output is correct
17 Correct 19 ms 588 KB Output is correct
18 Correct 22 ms 588 KB Output is correct
19 Correct 19 ms 652 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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