oj.uz

Submission #98137

# Submission time Handle Problem Language Result Execution time Memory
98137 2019-02-21T01:39:55 Z luciocf Chase (CEOI17_chase) C++14
40 / 100
 496 ms 2296 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;
const int maxv = 110;

typedef long long ll;

int n, c;
int num[maxn];

ll soma[maxn], dp[maxn][maxv][2];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	for (auto v: grafo[u])
	{
		if (v == p) continue;

		ll x = (ll)soma[v]-(ll)num[u];

		for (int i = 0; i <= c; i++)
		{
			dp[v][i][0] = max(dp[u][i][0], dp[u][i][1]);

			if (!i) continue;

			dp[v][i][1] = dp[u][i-1][0];
			dp[v][i][1] = x+max(dp[v][i][1], dp[u][i-1][1]);
		}

		dfs(v, u);
	}
}

int main(void)
{
	cin >> n >> c;

	for (int i = 1; i <= n; i++)
		cin >> num[i];

	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;

		grafo[u].push_back(v); grafo[v].push_back(u);
	}

	for (int u = 1; u <= n; u++)
		for (auto v: grafo[u])
			soma[u] += (ll)num[v];

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
	{
		memset(dp, 0, sizeof dp);

		dp[i][1][1] = soma[i];

		dfs(i, 0);

		for (int j = 1; j <= n; j++)
			for (int l = 0; l <= c; l++)
				ans = max({ans, dp[j][l][0], dp[j][l][1]});
	}

	cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 4 ms 2048 KB Output is correct
3 Correct 4 ms 2176 KB Output is correct
4 Correct 5 ms 2176 KB Output is correct
5 Correct 5 ms 2176 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 4 ms 2048 KB Output is correct
3 Correct 4 ms 2176 KB Output is correct
4 Correct 5 ms 2176 KB Output is correct
5 Correct 5 ms 2176 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct
7 Correct 485 ms 2252 KB Output is correct
8 Correct 138 ms 2220 KB Output is correct
9 Correct 135 ms 2296 KB Output is correct
10 Correct 496 ms 2296 KB Output is correct
11 Correct 242 ms 2176 KB Output is correct
12 Correct 159 ms 2176 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2048 KB Output is correct
2 Correct 4 ms 2048 KB Output is correct
3 Correct 4 ms 2176 KB Output is correct
4 Correct 5 ms 2176 KB Output is correct
5 Correct 5 ms 2176 KB Output is correct
6 Correct 4 ms 2048 KB Output is correct
7 Correct 485 ms 2252 KB Output is correct
8 Correct 138 ms 2220 KB Output is correct
9 Correct 135 ms 2296 KB Output is correct
10 Correct 496 ms 2296 KB Output is correct
11 Correct 242 ms 2176 KB Output is correct
12 Correct 159 ms 2176 KB Output is correct
13 Runtime error 5 ms 560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Halted 0 ms 0 KB -