Submission #47224

#	Time	Username	Problem	Language	Result	Execution time	Memory
47224		robert	Chase (CEOI17_chase)	C++14	70 / 100	997 ms	197880 KiB

chase

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef vector<long long> vi;

vector<vi> g;
vector<vector<vector<long long> > > m;
vi d;
//gives the max difference
long long solve(long long n, long long p, long long v){
	if(v==0)
		return 0;
//	if(m[n][p][v]!=-1)
//		return m[n][p][v];
	long long sum = 0;
	for(long long x=0; x<g[n].size(); x++){
		if(g[n][x]!=p){
			sum += d[g[n][x]];
		}
	}
	long long sol = sum;
	for(long long x=0; x<g[n].size(); x++){
		if(g[n][x]!=p){
			if(m[n][x][v]==-1)
				m[n][x][v] = solve(g[n][x], n, v);
			if(m[n][x][v-1]==-1)
				m[n][x][v-1] = solve(g[n][x], n, v-1);
			sol = max(sol, max(sum+m[n][x][v-1], m[n][x][v]));
		}
	}
	return sol;//m[n][p][v] = sol;
}

int main(){
	iostream::sync_with_stdio(false); cin.tie(0);
//	memset(m, -1, sizeof(m));
	long long N, V; cin>>N>>V;
	g.assign(N+1, vi());
	d.assign(N+1, 0);
	long long A, B;
	for(long long n=1; n<=N; n++)
		cin>>d[n];
	for(long long n=1; n<N; n++){
		cin>>A>>B;
		g[A].push_back(B);
		g[B].push_back(A);
	}
	m.assign(N+1, vector<vector<long long> >());
	for(int x=1; x<=N; x++)
		m[x].assign(g[x].size(), vector<long long>(110, -1));
	long long sol = 0;
	sol = solve(1, 0, V);
	for(long long x=2; x<=N&&N<10000; x++)
		sol = max(sol, solve(x, 0, V));
	cout << sol << endl;
	return 0;
}

Compilation message (stderr)

chase.cpp: In function 'long long int solve(long long int, long long int, long long int)':
chase.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long x=0; x<g[n].size(); x++){
                     ~^~~~~~~~~~~~
chase.cpp:25:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(long long x=0; x<g[n].size(); x++){
                     ~^~~~~~~~~~~~

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