oj.uz

답안 #939605

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
939605 2024-03-06T15:00:43 Z vjudge1 Chase (CEOI17_chase) C++17
40 / 100
 236 ms 7556 KB 
#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=1005;
vector <int> g[N];
int fr_sum[N],x[N];
int dp[N][N];
int n,k;
void dfs(int v,int p){
    for(auto to : g[v]){
        if(to!=p){
            for(int i=1;i<=k;i++)dp[to][i]=max(dp[v][i],dp[v][i-1]+fr_sum[to]-x[v]);
            dfs(to,v);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio();
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i];
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        fr_sum[v]+=x[u];
        fr_sum[u]+=x[v];
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int t=0;t<=k;t++){
                dp[j][t]=0;
            }
        }
        for(int j=1;j<=k;j++){
            dp[i][j]=fr_sum[i];
        }
        dfs(i,0);
        for(int j=1;j<=n;j++){
            for(int t=0;t<=k;t++){
                ans=max(ans,dp[j][t]);
            }
        }
    }
    cout<<ans<<"\n";
}
/*
 12 2
 2 3 3 8 1 5 6 7 8 3 5 4
 2 1
 2 7
 3 4
 4 7
 7 6
 5 6
 6 8
 6 9
 7 10
 10 11
 10 12
*/

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 232 ms 7516 KB Output is correct
8 Correct 21 ms 7516 KB Output is correct
9 Correct 25 ms 7556 KB Output is correct
10 Correct 236 ms 7516 KB Output is correct
11 Correct 82 ms 7512 KB Output is correct
12 Correct 31 ms 7512 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 232 ms 7516 KB Output is correct
8 Correct 21 ms 7516 KB Output is correct
9 Correct 25 ms 7556 KB Output is correct
10 Correct 236 ms 7516 KB Output is correct
11 Correct 82 ms 7512 KB Output is correct
12 Correct 31 ms 7512 KB Output is correct
13 Runtime error 2 ms 604 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -