제출 #101554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
101554		jamielim	Chase (CEOI17_chase)	C++14	0 / 100	1921 ms	51696 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];
int dp(int x,int vleft,int p){
    if(memo[x][vleft]!=-1)return memo[x][vleft];
    if(vleft==0)return memo[x][0]=0;
    if(adj[x].size()==0)return memo[x][vleft]=pigeons[x]-(p==-1?0:arr[p]);
    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),dp(adj[x][i],vleft-1,x)+pigeons[x]-(p==-1?0:arr[p])));
    }
    return memo[x][vleft]=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]=-1;
                }
            }
            ans=max(ans,dp(i,v,-1));
        }
        printf("%d",ans);
        return 0;
    }
    memset(memo,-1,sizeof(memo));
    printf("%d",dp(0,v,-1));
}

컴파일 시 표준 에러 (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