fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 5e2 + 5;
  5. const long long MaxK = 5e2 + 5;
  6. const long long INF = 1e18;
  7.  
  8. long long n,L,a[MaxN][MaxN],S[MaxN],dp[MaxN][MaxK];
  9. vector<long long> vt[MaxN];
  10. long long cur[MaxK], pre[MaxK];
  11. void dfs(long long u,long long par)
  12. {
  13.     for(long long v : vt[u])
  14.     {
  15.         if(v==par) continue;
  16.         dfs(v,u);
  17.     }
  18.  
  19.     memset(cur,-0x3f,sizeof(cur));
  20.     cur[0]=0;
  21.  
  22.     for(long long v : vt[u])
  23.     {
  24.         if(v==par) continue;
  25.  
  26.         for(long long j=0;j<=L;j++)
  27.         {
  28.             pre[j]=cur[j];
  29.             cur[j]=-INF;
  30.         }
  31.  
  32.         for(long long j=0;j<=L;j++)
  33.         {
  34.             for(long long k=0;k<=L-j;k++)
  35.             {
  36.                 cur[j+k]=max(cur[j+k],pre[j]+dp[v][k]);
  37.             }
  38.         }
  39.     }
  40.  
  41.     for(long long k=0;k<=min(L,S[u]);k++)
  42.     {
  43.         for(long long x=0;x<=k;x++)
  44.         {
  45.             dp[u][k]=max(dp[u][k],cur[k-x]+a[u][x]);
  46.         }
  47.     }
  48.  
  49. }
  50.  
  51. void input()
  52. {
  53.     cin>>n>>L;
  54.  
  55.     for(long long i=2;i<=n;i++)
  56.     {
  57.         long long p;
  58.         cin>>p;
  59.         vt[p].push_back(i);
  60.         vt[i].push_back(p);
  61.     }
  62.  
  63.     for(long long i=1;i<=n;i++)
  64.     {
  65.         cin>>S[i];
  66.     }
  67.  
  68.     for(long long i=1;i<=n;i++)
  69.     {
  70.         for(long long j=0;j<=L;j++)
  71.         {
  72.             cin>>a[i][j];
  73.         }
  74.     }
  75. }
  76.  
  77. void solve()
  78. {
  79.     memset(dp,-0x3f,sizeof(dp));
  80.  
  81.     dfs(1,0);
  82.  
  83.     long long ans=0;
  84.  
  85.     for(long long i=0;i<=L;i++)
  86.     {
  87.         ans=max(ans,dp[1][i]);
  88.     }
  89.  
  90.     cout<<ans;
  91. }
  92.  
  93. int main()
  94. {
  95.     ios_base::sync_with_stdio(0);
  96.     cin.tie(0);
  97.  
  98.     input();
  99.     solve();
  100. }
  101.  
Success #stdin #stdout 0.01s 7212KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KXlyYj
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!