Submission #939576

#TimeUsernameProblemLanguageResultExecution timeMemory
939576BaytoroChase (CEOI17_chase)C++17
100 / 100
247 ms180052 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define fr first #define sc second #define ll long long #define int long long const int N=1e5+5; int p[N]; vector<int> g[N]; int c[N][105],b[N][105]; int G(int x){ //int res=-=p[par]; int res=0;//<--------------- for(auto it: g[x]){ res+=p[it]; } return res; } int n,k; int ans=0; void dfs(int x, int par){ int sum=G(x); b[x][1]=sum; for(auto it: g[x]){ if(it==par) continue; dfs(it,x); for(int j=1;j<=k;j++){ ans=max(ans,b[x][j]+c[it][k-j]); c[x][j]=max(c[x][j],max(c[it][j],c[it][j-1]+sum-p[par])); b[x][j]=max(b[x][j],max(b[it][j],b[it][j-1]+sum-p[it])); } } reverse(all(g[x])); memset(c[x],0,sizeof c[x]); memset(b[x],0,sizeof b[x]); b[x][1]=sum; for(auto it: g[x]){ if(it==par) continue; for(int j=1;j<=k;j++){ ans=max(ans,b[x][j]+c[it][k-j]); c[x][j]=max(c[x][j],max(c[it][j],c[it][j-1]+sum-p[par])); b[x][j]=max(b[x][j],max(b[it][j],b[it][j-1]+sum-p[it])); } } } void solve(){ //int n,k; cin>>n>>k; for(int i=1;i<=n;i++) cin>>p[i]; for(int i=1;i<n;i++){ int a,b;cin>>a>>b; g[a].pb(b); g[b].pb(a); } dfs(1,0); cout<<ans<<endl; } main(){ int T=1; //cin>>T; while(T--){ solve(); } } /* 12 2 2 3 3 8 1 5 6 7 8 3 5 4 2 1 2 7 3 4 4 7 7 6 5 6 6 8 6 9 7 10 10 11 10 12 */

Compilation message (stderr)

chase.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   66 | main(){
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...