Submission #35789

#	Time	Username	Problem	Language	Result	Execution time	Memory
35789		ainta	Chase (CEOI17_chase)	C++14	100 / 100	316 ms	188392 KiB

chase

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n, K, X[101000];
long long S[101000], D1[101000][110], D2[101000][110], T1[110], T2[110], Res;
vector<int>E[101000];
void DFS(int a, int pp) {
	int i, x, j, k;
	D1[a][1] = S[a];
	for (i = 0; i < E[a].size(); i++) {
		x = E[a][i];
		if (x == pp)continue;
		DFS(x, a);
		for (j = 1; j <= K; j++) {
			long long d1 = max(D1[x][j], D1[x][j - 1] + S[a] - X[x]), d2 = max(D2[x][j], D2[x][j - 1] + S[x] - X[a]);
			T1[j] = d1, T2[j] = d2;
			if (j != K) {
				Res = max(Res, max(D1[a][K - j] + d2, D2[a][K - j] + d1));
				Res = max(Res, D2[x][j] + S[a]);
			}
		}
		for (j = 1; j <= K; j++) {
			D1[a][j] = max(D1[a][j], T1[j]);
			D2[a][j] = max(D2[a][j], T2[j]);
			Res = max(Res, D1[a][j]);
		}
	}
}
int main() {
	int i, a, b;
	scanf("%d%d", &n, &K);
	for (i = 1; i <= n; i++) {
		scanf("%d", &X[i]);
	}
	for (i = 1; i < n; i++) {
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
		S[a] += X[b], S[b] += X[a];
	}
	if (!K) {
		printf("0\n");
		return 0;
	}
	DFS(1, 0);
	printf("%lld\n", Res);
}

Compilation message (stderr)

chase.cpp: In function 'void DFS(int, int)':
chase.cpp:11:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < E[a].size(); i++) {
                ^
chase.cpp:9:15: warning: unused variable 'k' [-Wunused-variable]
  int i, x, j, k;
               ^
chase.cpp: In function 'int main()':
chase.cpp:32:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &K);
                       ^
chase.cpp:34:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &X[i]);
                     ^
chase.cpp:37:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
                        ^

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