oj.uz

답안 #107037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107037 2019-04-21T13:44:59 Z maksim_gaponov Fireworks (APIO16_fireworks) C++14
19 / 100
 52 ms 1916 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define len(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define pb push_back

const int MOD = 1e9 + 7;

int mod(int x) {
	x %= MOD;
	if (x < 0)
		x += MOD;
	return x;
}


const int MAXN = 310;
const int MAXA = 310;
const int INF = 1e18;

vector<vector<int>> g;
vector<vector<int>> dp;
vector<int> p;
vector<int> c;

void dfs(int u) {
	dp[u].resize(MAXA, INF);
	vector<int> sums(MAXA);
	for (auto v : g[u]) {
		dfs(v);
		for (int i = 0; i < MAXA; ++i) {
			sums[i] += dp[v][i];
		}
	}
	if (!len(g[u])) {
		for (int i = 0; i < MAXA; ++i) {
			dp[u][i] = abs(i - c[u]);
		}
		return;
	}
	for (int x = 0; x < MAXA; ++x) {
		for (int y = 0; y <= x; ++y) {
			if (u == 0 && x != y)
				continue;
			int new_c = x - y;
			dp[u][x] = min(dp[u][x], abs(c[u] - new_c) + sums[y]);
		}
	}
}

void run() {
	int n, m;
	cin >> n >> m;
	g.resize(n + m);
	dp.resize(n + m);
	vector<int> v;
	p.resize(n + m);
	c.resize(n + m);
	p[0] = -1;
	for (int i = 1; i < n + m; ++i) {
		cin >> p[i] >> c[i];
		--p[i];
		g[p[i]].pb(i);
		v.pb(c[i]);
	}
	if (false && n == 1) {
		sort(all(v));
		int X = v[len(v) / 2];
		int ans = 0;
		for (int i = 0; i < len(v); ++i) {
			ans += abs(v[i] - X);
		}
		cout << ans << '\n';
		return;
	} else {
		dfs(0);
		int ans = INF;
		for (auto val : dp[0])
			ans = min(ans, val);
		cout << ans << '\n';
		return;
	}
}

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
}

Subtask #1
0 / 7.0

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

Subtask #2
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 428 KB Output is correct
3 Correct 7 ms 512 KB Output is correct
4 Correct 17 ms 768 KB Output is correct
5 Correct 13 ms 512 KB Output is correct
6 Correct 12 ms 684 KB Output is correct
7 Correct 14 ms 740 KB Output is correct
8 Correct 16 ms 768 KB Output is correct
9 Correct 16 ms 760 KB Output is correct
10 Correct 19 ms 888 KB Output is correct
11 Correct 22 ms 896 KB Output is correct
12 Correct 18 ms 1024 KB Output is correct
13 Correct 27 ms 1024 KB Output is correct
14 Correct 52 ms 1916 KB Output is correct
15 Correct 23 ms 1024 KB Output is correct
16 Correct 21 ms 1016 KB Output is correct
17 Correct 31 ms 1016 KB Output is correct
18 Correct 26 ms 1024 KB Output is correct
19 Correct 23 ms 1036 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 45.0

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