oj.uz

Submission #200603

# Submission time Handle Problem Language Result Execution time Memory
200603 2020-02-07T14:26:24 Z mamadmokhi Dostavljač (COCI18_dostavljac) C++17
140 / 140
 533 ms 10532 KB 
     // 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++)
        {
         dp[x][i][1][0]=dp[x][i-1][0][0]+na[x];
        dp[x][i][1][1]=dp[x][i-1][0][1]+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];
        }

        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;
            }
        }

    }
    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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 760 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1144 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 888 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2296 KB Output is correct
2 Correct 9 ms 1528 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1656 KB Output is correct
2 Correct 81 ms 4148 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 5240 KB Output is correct
2 Correct 44 ms 3448 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 4088 KB Output is correct
2 Correct 332 ms 7416 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 8416 KB Output is correct
2 Correct 113 ms 6136 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 10532 KB Output is correct
2 Correct 53 ms 5404 KB Output is correct