Submission #1247511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247511		MateiKing80	Chase (CEOI17_chase)	C++20	0 / 100	317 ms	174012 KiB

chase

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

const int N = 1e5 + 5, V = 105, inf = 1e16;

int dp[2][V][N], p[N], v, ans;
vector<int> vec[N];

void dfs(int nod, int papa) {
	int sum = 0;
	for (auto i : vec[nod]) {
		if (i == papa)
			continue;
		sum += p[i];
	}
	for (int i = 0; i <= v; i ++) {
		dp[0][i][nod] = max(dp[0][i][papa], dp[1][i][papa]);
		if (i)
			dp[1][i][nod] = max(dp[1][i - 1][nod] + sum, dp[0][i - 1][nod] + sum);
	}
	for (auto i : vec[nod])
		if (i != papa)
			dfs(i, nod);
}

signed main() {
	int n;
	cin >> n >> v;
	for (int i = 1; i <= n; i ++)
		cin >> p[i];
	memset(dp, -inf, sizeof(dp));
	for (int i = 1; i < n; i ++) {
		int x, y;
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	dp[0][0][1] = 0;
	dp[1][1][1] = 0;
	for (auto i : vec[1])
		dp[1][1][1] += p[i];
	for (auto i : vec[1])
		dfs(i, 1);
	for (int i = 1; i <= n; i ++)
		for (int j = 0; j <= v; j ++)
			ans = max(ans, max(dp[0][j][i], dp[1][j][i]));
	cout << ans << '\n';
}

/*
cred ca problema este ca poti sari cateva locuri in care nu pui paine
si se schimba dinamica
avem o alta dinamica de tipul: dp1[0/1], dp2[0/1] ca inainte dar [0/1] inseamna ca
*/

/*
subtaskforces
deci
bag ala de pleaca de la 1
dp[nod][val][0/1] best thing pana la nod + am luat sau nu nod
*/

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:35:20: warning: overflow in conversion from 'long long int' to 'int' changes value from '-10000000000000000' to '-1874919424' [-Woverflow]
   35 |         memset(dp, -inf, sizeof(dp));
      |                    ^~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30