oj.uz

Submission #939605

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -