Submission #258044

#	Time	Username	Problem	Language	Result	Execution time	Memory
258044		uacoder123	Dostavljač (COCI18_dostavljac)	C++14	140 / 140	969 ms	2512 KiB

dostavljac

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14