oj.uz

Submission #258044

# Submission time Handle Problem Language Result Execution time Memory
258044 2020-08-05T09:07:31 Z uacoder123 Dostavljač (COCI18_dostavljac) C++14
140 / 140
 969 ms 2512 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)

typedef long long int lli;
typedef pair <int, int> ii;
typedef vector <int> vi;
int n,m;
vi al[501];
int dp[501][501][2],val[501];
void dfs(int node,int p)
{
  for(int i=0;i<al[node].size();++i)
    if(al[node][i]!=p)
      dfs(al[node][i],node);
  dp[node][0][0]=0;
  dp[node][0][1]=0;
  for(int i=1;i<=m;++i)
  {
    dp[node][i][0]=val[node];
    dp[node][i][1]=val[node];
  }
  for(int i=0;i<al[node].size();++i)
  {
    for(int j=m;j>=1;--j)
    {
      for(int k=j;k>=0;--k)
      {
        if(j-2>=k)
        {
          dp[node][j][0]=max(dp[node][j][0],dp[al[node][i]][k][0]+dp[node][j-2-k][0]);
          dp[node][j][1]=max(dp[node][j][1],dp[node][j-2-k][1]+dp[al[node][i]][k][0]);
        }
        if(j-1>=k)
        {
          dp[node][j][1]=max(dp[node][j][1],dp[al[node][i]][k][1]+dp[node][j-1-k][0]);
        }
      }
    }
  }
}
int main()
{
  cin>>n>>m;
  for(int i=1;i<=n;++i)
    cin>>val[i];
  for(int i=0;i<n-1;++i)
  {
    int f,s;
    cin>>f>>s;
    al[f].pb(s);
    al[s].pb(f);
  }
  dfs(1,1);
  cout<<dp[1][m][1]<<endl;
  return 0;
}

Compilation message

dostavljac.cpp: In function 'void dfs(int, int)':
dostavljac.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
dostavljac.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 764 KB Output is correct
2 Correct 9 ms 896 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 984 KB Output is correct
2 Correct 139 ms 888 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 1148 KB Output is correct
2 Correct 77 ms 1144 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1528 KB Output is correct
2 Correct 589 ms 1528 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 1912 KB Output is correct
2 Correct 204 ms 2040 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 969 ms 2512 KB Output is correct
2 Correct 89 ms 2296 KB Output is correct