Submission #245810

#	Time	Username	Problem	Language	Result	Execution time	Memory
245810		kshitij_sodani	Chase (CEOI17_chase)	C++17	0 / 100	386 ms	331748 KiB

chase

/*
https://www.oi.edu.pl/old/ioi/downloads/ioi2005-tasks-and-solutions-a5.pdf
*/
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//#define endl '\n'
llo n,m;
llo it[100001];
llo co[100001];
vector<llo> adj[100001];
llo dp[100001][101][2];
llo dp2[100001][101][2];
llo ans=0;
void dfs(llo no,llo par2=-1){
	for(llo i=1;i<=m;i++){
		dp[no][i][1]=co[no];
		dp2[no][i][1]=co[no];
	}
//	vector<pair<llo,llo>> ac[m+1][2];
	for(auto j:adj[no]){
		if(j==par2){
			continue;
		}
		dfs(j,no);
		for(llo i=0;i<=m;i++){
			llo x=0;
			llo y=0;
			if(i>0){
				x=max(x,dp[j][i-1][0]+co[no]);
				if(i>1){
					x=max(x,dp[j][i-1][i]+co[no]-it[j]);
				}
			}
			dp[no][i][1]=max(dp[no][i][1],x);

			y=max(y,dp[j][i][0]);
			if(i>0){
				y=max(y,dp[no][i][1]-it[no]);
			}
			dp[no][i][0]=max(dp[no][i][0],y);
	//		ac[i][0].pb({max(x,y),j});
			x=0;
			y=0;

			if(i>0){
				x=max(x,dp[j][i-1][0]+co[no]-it[no]);
				if(i>1){
					x=max(x,dp[j][i-1][1]+co[no]-it[no]);
				}
				y=max(y,dp2[j][i][1]);
			}
			y=max(y,dp2[j][i][0]);
			dp2[no][i][0]=max(dp2[no][i][0],y);
			dp2[no][i][1]=max(dp2[no][i][1],x);
	//		ac[i][1].pb({max(x,y),j});
		}
	}
	ans=max(ans,dp[no][m][0]);
	ans=max(ans,dp[no][m][1]);
	ans=max(ans,dp2[no][m][0]);
	ans=max(ans,dp2[no][m][1]);
/*	for(llo i=0;i<=m;i++){
		if(ac[i][0].size()>0 and ac[m-i][1].size()>0){
			if(ac[i][0][0].b==ac[m-i][1][0].b){
				if(ac[i][0].size()>1){
					ans=max(ans,ac[i][0][1].a+ac[m-i][1][0].a);
				}
				if(ac[m-i][1].size()>1){
					ans=max(ans,ac[i][0][0].a+ac[m-i][1][1].a);
				}
			}
			else{
				ans=max(ans,ac[i][0][0].a+ac[m-i][1][0].a);
			}
		}
	}
*/



}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	for(llo i=0;i<n-1;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		adj[aa].pb(bb);
		adj[bb].pb(aa);
		co[aa]+=it[bb];
		co[bb]+=it[aa];
	}
	dfs(0);
	cout<<ans<<endl;


	return 0;
}

Compilation message (stderr)

chase.cpp: In function 'void dfs(llo, llo)':
chase.cpp:36:26: warning: array subscript is above array bounds [-Warray-bounds]
      x=max(x,dp[j][i-1][i]+co[no]-it[j]);
              ~~~~~~~~~~~~^

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