oj.uz

Submission #899941

# Submission time Handle Problem Language Result Execution time Memory
899941 2024-01-07T10:31:13 Z alexdd Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 94020 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k,rez;
int p[100005];
int dp[100005][105];
int aux[105];
int aux2[105];
vector<int> con[100005];
void dfs(int nod, int par)
{
    int sump=0;
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            dfs(adj,nod);
            sump += p[adj];
        }
    }
    for(int i=0;i<=k;i++)
        dp[nod][i]=aux[i]=aux2[i]=0;
    dp[nod][1] = sump + p[par];
    for(auto adj:con[nod])
    {
        if(adj!=par)
        {
            for(int i=1;i<=k;i++)
            {
                dp[nod][i] = max(dp[nod][i], dp[adj][i]);
                dp[nod][i] = max(dp[nod][i], dp[adj][i-1] + sump + p[par] - p[adj]);
            }
        }
    }
    for(int i=1;i<=k;i++)
    {
        dp[nod][i] = max(dp[nod][i], dp[nod][i-1]);
        rez = max(rez, dp[nod][i]);
        //cout<<nod<<" "<<i<<"   "<<dp[nod][i]<<"\n";
    }
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>p[i];
    int a,b;
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        con[a].push_back(b);
        con[b].push_back(a);
    }
    for(int i=1;i<=n;i++)
        dfs(i,0);
    cout<<rez;
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4728 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4728 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 513 ms 4812 KB Output is correct
8 Correct 37 ms 4812 KB Output is correct
9 Correct 28 ms 4788 KB Output is correct
10 Correct 518 ms 4776 KB Output is correct
11 Correct 164 ms 4776 KB Output is correct
12 Correct 54 ms 4700 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4061 ms 94020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4728 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 513 ms 4812 KB Output is correct
8 Correct 37 ms 4812 KB Output is correct
9 Correct 28 ms 4788 KB Output is correct
10 Correct 518 ms 4776 KB Output is correct
11 Correct 164 ms 4776 KB Output is correct
12 Correct 54 ms 4700 KB Output is correct
13 Execution timed out 4061 ms 94020 KB Time limit exceeded
14 Halted 0 ms 0 KB -