Submission #200590

#	Time	Username	Problem	Language	Result	Execution time	Memory
200590		mamadmokhi	Dostavljač (COCI18_dostavljac)	C++17	0 / 140	517 ms	10668 KiB

dostavljac

     // give up :((((
    #include <bits/stdc++.h>
    #define mp make_pair
    #define f1 first
    #define f2 second
    #define pb push_back
    #define int long long
    #define pii pair<int ,int>
    #define ios  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    using namespace std;
    const int mox=500+9;
    int dp[mox][mox][2][2];
    int na[mox];
    vector<int> v[mox];
    int n,m;
    int dp2[mox][mox][2][2];
    void dfs(int x ,int dad=-1)
    {
        for(int i:v[x])
        {
            if(i!=dad)
            {
                dfs(i,x);
            }
        }
        int r=v[x].size();
        for(int i=2 ; i<=m ; i++)
        {
           for(int j=1 ; j<=r ; j++)
           {
               if(v[x][j-1]!=dad)
               {
                   for(int p=0 ; p<=i-2 ; p++)
                   {
                       dp2[i][j][0][1]=max(max(dp[v[x][j-1]][p][0][1]+dp2[i-p-2][j-1][0][1],dp[v[x][j-1]][p][1][1]+dp2[i-p-2][j-1][0][1]),dp2[i][j][0][1]);
                       dp2[i][j][0][0]=max(max(dp[v[x][j-1]][p][0][0]+dp2[i-p-1][j-1][0][1],dp[v[x][j-1]][p][1][0]+dp2[i-p-1][j-1][0][1]),dp2[i][j][0][0]);
                       dp2[i][j][0][0]=max(max(dp[v[x][j-1]][p][0][1]+dp2[i-p-2][j-1][0][0],dp[v[x][j-1]][p][1][1]+dp2[i-p-2][j-1][0][0]),dp2[i][j][0][0]);
                   }
                   dp2[i][j][0][1]=max(dp2[i][j][0][1],dp2[i][j-1][0][1]);
                   dp2[i][j][0][0]=max(dp2[i][j][0][0],dp2[i][j-1][0][0]);
                dp2[i][j][0][0]=max(max(dp[v[x][j-1]][i-1][0][0],dp[v[x][j-1]][i-1][1][0]),dp2[i][j][0][0]);
               }
               else
               {
                   dp2[i][j][0][1]=dp2[i][j-1][0][1];
                   dp2[i][j][0][0]=dp2[i][j-1][0][0];
               }

           }
        }
        for(int i=2 ; i<=m ; i++)
        {
            for(int j=1 ; j<=r ; j++)
            {
                dp2[i][j][0][1]=0;
                dp2[i][j][0][0]=0;
            }
        }
        for(int i=2 ; i<=m ; i++)
        {
         dp[x][i][1][0]=dp[x][i-1][0][0]+na[x];
        dp[x][i][1][1]=dp[x][i-1][0][0]+na[x];
        dp[x][i][0][0]=dp2[i][v[x].size()][0][0];
       dp[x][i][0][1]=dp2[i][v[x].size()][0][1];
        }

    }
    int32_t main()
    {
           ios

           cin>>n>>m;
           for(int i=1 ; i<=n ; i++)
           {
               cin>>na[i];
           }
           for(int i=0 ; i<n-1 ; i++)
           {
               int a,b;
               cin>>a>>b;
               v[a].pb(b);
               v[b].pb(a);
           }
           for(int i=1 ; i<=n ; i++)
           {
               dp[i][1][1][1]=na[i];
               dp[i][1][1][0]=na[i];
           }
           dfs(1);
          cout<<max(dp[1][m][0][0],dp[1][m][1][0]);
    }

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14