Submission #308509

#	Time	Username	Problem	Language	Result	Execution time	Memory
308509		shivensinha4	Dostavljač (COCI18_dostavljac)	C++17	0 / 140	42 ms	2432 KiB

dostavljac

#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];
	int cret[t+2], cnoret[t+2];
	
	for (int i: adj[p]) if (i != parent) {
		dfs(i, p);
		
		for_(j, 0, t+1) {
			cret[j] = ret[p][j];
			cnoret[j] = noret[p][j];
		}
		for_(a, 0, t) {
			if (ret[p][a]) 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]);
			}
			if (noret[p][a]) 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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14