oj.uz

Submission #80163

# Submission time Handle Problem Language Result Execution time Memory
80163 2018-10-19T09:53:23 Z aminra Chase (CEOI17_chase) C++14
70 / 100
 609 ms 178296 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 7;
const int MAXS = (int)107;
const int infint = (int)1e9;
const ll inf = 1e18;
ll n, v, dp[MAXN][MAXS][2], P[MAXN], val[MAXN];
vector<ll> G[MAXN];
void dfs(int u, int p)
{
	if(p == -1)
	{
		dp[u][0][0] = 0;
		dp[u][1][1] = val[u];
	}
	else
	{
		for (int j = 0; j <= v; j++)
		{
			dp[u][j][0] = max(dp[p][j][1], dp[p][j][0]);
			if(j)
				dp[u][j][1] = max(dp[p][j - 1][0] + val[u] - P[p], dp[p][j - 1][1] + val[u] - P[p]);
		}
	}
	for (auto v : G[u])
		if(v != p)
			dfs(v, u);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> v;
	for (int i = 1; i <= n; i++)
		cin >> P[i];
	for (int i = 0; i < n - 1; i++)
	{
		ll u, v;
		cin >> u >> v;
		val[v] += P[u];
		val[u] += P[v];
		G[u].push_back(v);
		G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= v; j++)
			dp[i][j][0] = -inf, dp[i][j][1] = -inf;
	if(n <= 1000)
	{
		ll ans = 0;
		for (int root = 1; root <= n; root++)
		{
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= v; j++)
					dp[i][j][0] = -inf, dp[i][j][1] = -inf;
			dfs(root, -1);
			for (int i = 1; i <= n; i++)
				for (int j = 0; j <= v; j++)
					ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
		}
		cout << ans;
		return 0;
	}
	ll root = 1;
	dfs(root, -1);
	ll ans = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= v; j++)
		{
			ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
		}
	cout << ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct
5 Correct 4 ms 2812 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct
5 Correct 4 ms 2812 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct
7 Correct 571 ms 4748 KB Output is correct
8 Correct 61 ms 4748 KB Output is correct
9 Correct 49 ms 4748 KB Output is correct
10 Correct 609 ms 4748 KB Output is correct
11 Correct 245 ms 4748 KB Output is correct
12 Correct 106 ms 4812 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 178172 KB Output is correct
2 Correct 277 ms 178296 KB Output is correct
3 Correct 246 ms 178296 KB Output is correct
4 Correct 216 ms 178296 KB Output is correct
5 Correct 271 ms 178296 KB Output is correct
6 Correct 288 ms 178296 KB Output is correct
7 Correct 283 ms 178296 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2680 KB Output is correct
2 Correct 4 ms 2812 KB Output is correct
3 Correct 4 ms 2812 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct
5 Correct 4 ms 2812 KB Output is correct
6 Correct 4 ms 2904 KB Output is correct
7 Correct 571 ms 4748 KB Output is correct
8 Correct 61 ms 4748 KB Output is correct
9 Correct 49 ms 4748 KB Output is correct
10 Correct 609 ms 4748 KB Output is correct
11 Correct 245 ms 4748 KB Output is correct
12 Correct 106 ms 4812 KB Output is correct
13 Correct 275 ms 178172 KB Output is correct
14 Correct 277 ms 178296 KB Output is correct
15 Correct 246 ms 178296 KB Output is correct
16 Correct 216 ms 178296 KB Output is correct
17 Correct 271 ms 178296 KB Output is correct
18 Correct 288 ms 178296 KB Output is correct
19 Correct 283 ms 178296 KB Output is correct
20 Incorrect 281 ms 178296 KB Output isn't correct
21 Halted 0 ms 0 KB -