Submission #101576

#	Time	Username	Problem	Language	Result	Execution time	Memory
101576		jamielim	Chase (CEOI17_chase)	C++14	0 / 100	3665 ms	93532 KiB

chase

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

int n,v;
vector<int> adj[100005];
int arr[100005];
int pigeons[100005];
int memo[100005][105][2];
int dp(int x,int vleft,int p,int subtract){
    if(memo[x][vleft][subtract]!=-1)return memo[x][vleft][subtract];
    if(vleft==0)return memo[x][0][subtract]=(subtract?-arr[x]:0);
    if(adj[x].size()==0)return memo[x][vleft][subtract]=pigeons[x]-(subtract?arr[x]:0);
    int ans=0;
    for(int i=0;i<(int)adj[x].size();i++){
        if(adj[x][i]==p)continue;
        ans=max(ans,max(dp(adj[x][i],vleft,x,0),dp(adj[x][i],vleft-1,x,1)+pigeons[x]-(subtract?arr[x]:0)));
    }
    return memo[x][vleft][subtract]=ans;
}

int main(){
    scanf("%d%d",&n,&v);
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    int a,b;
    for(int i=0;i<n-1;i++){
        scanf("%d%d",&a,&b); a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=0;i<n;i++){
        pigeons[i]=0;
        for(int j=0;j<(int)adj[i].size();j++){
            pigeons[i]+=arr[adj[i][j]];
        }
    }
    if(n<=1000){
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                for(int k=0;k<=v;k++){
                    memo[j][k][0]=-1;
                    memo[j][k][1]=-1;
                }
            }
            ans=max(ans,dp(i,v,-1,0));
        }
        printf("%d",ans);
        return 0;
    }
    memset(memo,-1,sizeof(memo));
    printf("%d",dp(0,v,-1,0));
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&v);
     ~~~~~^~~~~~~~~~~~~~
chase.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]);
         ~~~~~^~~~~~~~~~~~~~
chase.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b); a--; b--;
         ~~~~~^~~~~~~~~~~~~~

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