Submission #101589

#	Time	Username	Problem	Language	Result	Execution time	Memory
101589		jamielim	Chase (CEOI17_chase)	C++14	0 / 100	3767 ms	176512 KiB

chase

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

int n,v;
vector<int> adj[100005];
long long arr[100005];
long long pigeons[100005];
long long memo[100005][105][2];
long long dp(int x,int vleft,int p,int subtract){
    if(memo[x][vleft][subtract]!=1000000000000000010)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);
    long long 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){
        long long 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]=1000000000000000010;
                    memo[j][k][1]=1000000000000000010;
                }
            }
            ans=max(ans,dp(i,v,-1,0));
        }
        printf("%lld",ans);
        return 0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<=v;j++){
            memo[i][j][0]=1000000000000000010;
            memo[i][j][1]=1000000000000000010;
        }
    }
    long long ans=dp(0,v,-1,0);
    for(int i=0;i<50000000/n/v;i++){
        ans=max(ans,dp(rand()%n,v,-1,0));
    }
    printf("%lld",ans);
}

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:24:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&arr[i]);
                    ~~~~~~~^
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