oj.uz

Submission #45260

# Submission time Handle Problem Language Result Execution time Memory
45260 2018-04-12T09:23:05 Z qoo2p5 Chase (CEOI17_chase) C++17
70 / 100
 358 ms 89404 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;
const int CNT = 101;

int n, cc;
vector<int> g[N];
ll p[N], around[N];
ll dp[N][CNT];

void dfs(int v, int f = 0) {
	rep(i, 1, cc + 1) {
		dp[v][i] = max(dp[f][i], dp[f][i - 1] + around[v] - p[f]);
	}
	for (int u : g[v]) {
		if (u == f) {
			continue;
		}
		dfs(u, v);
	}
}

void run() {
	cin >> n >> cc;
	rep(i, 1, n + 1) {
		cin >> p[i];
	}
	rep(i, 0, n - 1) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	rep(i, 1, n + 1) {
		for (int j : g[i]) {
			around[i] += p[j];
		}
	}
	
	ll ans = 0;
	
	if (n <= 1000) {
		rep(st, 1, n + 1) {
			rep(i, 1, n + 1) rep(j, 0, cc + 1) dp[i][j] = 0;
			dfs(st);
			rep(i, 1, n + 1) {
				rep(j, 1, cc + 1) {
					maxi(ans, dp[i][j]);
				}
			}
		}
	} else {
		dfs(1);
		rep(i, 1, n + 1) {
			rep(j, 1, cc + 1) {
				maxi(ans, dp[i][j]);
			}
		}
	}
	cout << ans << "\n";
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2916 KB Output is correct
3 Correct 3 ms 2916 KB Output is correct
4 Correct 3 ms 3032 KB Output is correct
5 Correct 4 ms 3032 KB Output is correct
6 Correct 4 ms 3032 KB Output is correct
7 Correct 336 ms 3900 KB Output is correct
8 Correct 42 ms 3924 KB Output is correct
9 Correct 31 ms 3960 KB Output is correct
10 Correct 358 ms 3980 KB Output is correct
11 Correct 151 ms 4088 KB Output is correct
12 Correct 63 ms 4088 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 89336 KB Output is correct
2 Correct 182 ms 89404 KB Output is correct
3 Correct 129 ms 89404 KB Output is correct
4 Correct 130 ms 89404 KB Output is correct
5 Correct 179 ms 89404 KB Output is correct
6 Correct 187 ms 89404 KB Output is correct
7 Correct 204 ms 89404 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2916 KB Output is correct
3 Correct 3 ms 2916 KB Output is correct
4 Correct 3 ms 3032 KB Output is correct
5 Correct 4 ms 3032 KB Output is correct
6 Correct 4 ms 3032 KB Output is correct
7 Correct 336 ms 3900 KB Output is correct
8 Correct 42 ms 3924 KB Output is correct
9 Correct 31 ms 3960 KB Output is correct
10 Correct 358 ms 3980 KB Output is correct
11 Correct 151 ms 4088 KB Output is correct
12 Correct 63 ms 4088 KB Output is correct
13 Correct 213 ms 89336 KB Output is correct
14 Correct 182 ms 89404 KB Output is correct
15 Correct 129 ms 89404 KB Output is correct
16 Correct 130 ms 89404 KB Output is correct
17 Correct 179 ms 89404 KB Output is correct
18 Correct 187 ms 89404 KB Output is correct
19 Correct 204 ms 89404 KB Output is correct
20 Incorrect 222 ms 89404 KB Output isn't correct
21 Halted 0 ms 0 KB -