Submission #259771

#	Time	Username	Problem	Language	Result	Execution time	Memory
259771		MKopchev	Chase (CEOI17_chase)	C++14	100 / 100	783 ms	166368 KiB

chase

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42,vmax=1e2+5;

int n,put;

vector<int> adj[nmax];

long long sum[nmax],inp[nmax];

long long dp[2][vmax][nmax];//0-> up, 1-> down

long long outp;

void dfs(int node,int par)
{
    //cout<<"dfs "<<node<<" "<<par<<endl;

    //dp[0][1][node]=sum[node];
    dp[1][1][node]=sum[node];

    for(auto k:adj[node])
        if(k!=par)
        {
            dfs(k,node);

            for(int j=1;j<=put;j++)
            {
                long long add_1=max(dp[0][j][k],dp[0][j-1][k]+sum[k]-inp[node]);

                outp=max(outp,dp[1][put-j][node]+add_1);

                long long add_2=max(dp[1][j][k],dp[1][j-1][k]+sum[node]-inp[k]);

                outp=max(outp,dp[0][put-j][node]+add_2);
            }

        for(int j=put;j>=1;j--)
        {
            long long add_1=max(dp[0][j][k],dp[0][j-1][k]+sum[k]-inp[node]);
            long long add_2=max(dp[1][j][k],dp[1][j-1][k]+sum[node]-inp[k]);

            dp[0][j][node]=max(dp[0][j][node],add_1);
            dp[1][j][node]=max(dp[1][j][node],add_2);
        }

        for(int j=0;j<=put;j++)
        {
            outp=max(outp,dp[0][j][node]);
            outp=max(outp,dp[1][j][node]);
        }

        }
    /*
    cout<<"node= "<<node<<endl;
    for(int j=0;j<=put;j++)cout<<dp[0][j][node]<<" ";cout<<endl;
    for(int j=0;j<=put;j++)cout<<dp[1][j][node]<<" ";cout<<endl;
    */
}
int main()
{
    scanf("%i%i",&n,&put);

    for(int i=1;i<=n;i++)
        scanf("%lld",&inp[i]);

    for(int i=1;i<n;i++)
    {
        int u,v;
        scanf("%i%i",&u,&v);
        adj[u].push_back(v);
        adj[v].push_back(u);

        sum[u]+=inp[v];
        sum[v]+=inp[u];
    }

    dfs(1,0);

    printf("%lld\n",outp);
    return 0;
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i%i",&n,&put);
     ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&inp[i]);
         ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i%i",&u,&v);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30