oj.uz

Submission #308506

# Submission time Handle Problem Language Result Execution time Memory
308506 2020-10-01T12:53:14 Z shivensinha4 Dostavljač (COCI18_dostavljac) C++17
140 / 140
 194 ms 2388 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'

const int MXN = 501;
int n, t;
int ret[MXN+1][MXN+1], noret[MXN+1][MXN+1], val[MXN+1];
vi adj[MXN+1];

void dfs(int p, int parent) {
	ret[p][1] = noret[p][1] = val[p];
	
	for (int i: adj[p]) if (i != parent) {
		dfs(i, p);
		int cret[t+2], cnoret[t+2];
		
		for_(j, 0, t+1) {
			cret[j] = ret[p][j];
			cnoret[j] = noret[p][j];
		}
		for_(a, 0, t) {
			for_(b, 1, t-a) {
				if (ret[i][b] and a+b+2 <= t) cret[a+b+2] = max(cret[a+b+2], ret[p][a]+ret[i][b]);
				if (noret[i][b]) cnoret[a+b+1] = max(cnoret[a+b+1], ret[p][a]+noret[i][b]);
			}
			for_(b, 1, t-a-1) if (ret[b]) cnoret[a+b+2] = max(cnoret[a+b+2], noret[p][a]+ret[i][b]);
		}
		for_(j, 0, t+1) {
			ret[p][j] = cret[j];
			noret[p][j] = cnoret[j];
		}
	}
}


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> t;
	memset(ret, 0, sizeof(ret)); memset(noret, 0, sizeof(noret));
	
	for_(i, 0, n) cin >> val[i];
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a); 
	}
	
	dfs(0, 0);
	
	int ans = 0;
	for_(i, 0, t+1) ans = max({ans, noret[0][i], ret[0][i]});
	
	cout << ans << endl;

	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2304 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2304 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2304 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2336 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2304 KB Output is correct
2 Correct 3 ms 2304 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2304 KB Output is correct
2 Correct 26 ms 2304 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2304 KB Output is correct
2 Correct 18 ms 2304 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2304 KB Output is correct
2 Correct 98 ms 2388 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 2304 KB Output is correct
2 Correct 44 ms 2304 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 2304 KB Output is correct
2 Correct 17 ms 2304 KB Output is correct