oj.uz

Submission #401641

# Submission time Handle Problem Language Result Execution time Memory
401641 2021-05-10T15:44:01 Z BERNARB01 Fireworks (APIO16_fireworks) C++17
0 / 100
 6 ms 12236 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 5001;
const long long inf = (long long) 4e18L;

int n, m;
vector<pair<int, long long>> g[N];
long long dp[N][302];

long long sol(int u, int left) {
	if (g[u].size() == 0) {
		assert(left == 0);
		return 0;
	}
	long long& ret = dp[u][left];
	if (ret != -1) {
		return ret;
	}
	ret = 0;
	for (pair<int, long long> _p : g[u]) {
		long long sub = inf;
		int v = _p.first;
		long long w = _p.second;
		if (g[v].size() == 0) {
			sub = abs(w - left);
			ret += sub;
			continue;
		}
		for (int j = 0; j <= left; j++) {
			sub = min(sub, abs(w - j) + sol(v, left - j));
		}
		ret += sub;
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	long long res = 0;
	for (int i = 1; i < n + m; i++) {
		int p;
		long long c;
		cin >> p >> c;
		g[p - 1].emplace_back(i, c);
		res += c;
	}
	memset(dp, -1, sizeof dp);
	for (int i = 14; i < 15; i++) {
		res = min(res, sol(0, i));
	}
	cout << res << '\n';
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12236 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 12236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 12236 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 12236 KB Output isn't correct
2 Halted 0 ms 0 KB -