oj.uz

Submission #200590

# Submission time Handle Problem Language Result Execution time Memory
200590 2020-02-07T13:19:26 Z mamadmokhi Dostavljač (COCI18_dostavljac) C++17
0 / 140
 517 ms 10668 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++)
        {
            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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 504 KB Output isn't correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 632 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 1272 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 888 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 2168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 1656 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 5240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 4088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 301 ms 8468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 517 ms 10668 KB Output isn't correct
2 Halted 0 ms 0 KB -