oj.uz

Submission #780592

# Submission time Handle Problem Language Result Execution time Memory
780592 2023-07-12T10:35:58 Z vjudge1 Dostavljač (COCI18_dostavljac) C++17
140 / 140
 144 ms 2288 KB 
#include <bits/stdc++.h>

using namespace std;

vector < int > g[505];
int dp[505][505][2];
int cst[505];

void solve(int p,int u) {

    for (int i=0;i<g[u].size();i++) {
        int to=g[u][i];
        if (to == p) continue;
        solve(u,to);
        for (int now=500;now>=0;now--)
            for (int x=1;x+2+now<=503;x++) {
                dp[u][now+2+x][1]=max(dp[u][now+2+x][1],dp[u][now][1]+dp[to][x][1]);
                dp[u][now+2+x][0]=max(dp[u][now+2+x][0],dp[u][now][0]+dp[to][x][1]);
                dp[u][now+1+x][0]=max(dp[u][now+1+x][0],dp[u][now][1]+dp[to][x][0]);
                dp[u][now+1+x][0]=max(dp[u][now+1+x][0],dp[u][now][1]+dp[to][x][1]);
            }
    }

    for (int now=500;now>=1;now--)
        dp[u][now][0]=max(dp[u][now][0],dp[u][now-1][0]+cst[u]),
        dp[u][now][1]=max(dp[u][now][1],dp[u][now-1][1]+cst[u]);

}

int n,m,i,a,b,res;

int main() {
    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>cst[i];
    for (i=1;i<n;i++) {
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    solve(0,1);
    res=0;
    for (i=0;i<=m;i++)
        res=max(res,max(dp[1][i][0],dp[1][i][1]));
    cout<<res<<endl;
}

Compilation message

dostavljac.cpp: In function 'void solve(int, int)':
dostavljac.cpp:11:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for (int i=0;i<g[u].size();i++) {
      |                  ~^~~~~~~~~~~~
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
14.0 / 14.0

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

Subtask #4
14.0 / 14.0

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

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 672 KB Output is correct
2 Correct 30 ms 724 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 872 KB Output is correct
2 Correct 41 ms 812 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 1020 KB Output is correct
2 Correct 54 ms 1016 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 1440 KB Output is correct
2 Correct 87 ms 1484 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 1872 KB Output is correct
2 Correct 108 ms 1820 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 2288 KB Output is correct
2 Correct 139 ms 2228 KB Output is correct