oj.uz

Submission #961682

# Submission time Handle Problem Language Result Execution time Memory
961682 2024-04-12T10:12:47 Z LucaIlie Chase (CEOI17_chase) C++17
0 / 100
 318 ms 250508 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e5;
const int MAX_K = 100;
const long long INF = 1e15;
int k;
int a[MAX_N + 1];
long long b[MAX_N + 1];
long long dp[MAX_N + 1][MAX_K + 1][3];
vector<int> adj[MAX_N + 1];

long long maxCost = 0;
void dfs( int u, int p ) {
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }

    for ( int x = 1; x <= k; x++ )
        dp[u][x][0] = b[u] - a[u];
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;

        for ( int x = 0; x <= k; x++ ) {
            ///0 0
            maxCost = max( maxCost, dp[u][x][0] + dp[v][k - x][0] - a[u] - a[v] );
            ///0 1
            maxCost = max( maxCost, dp[u][x][0] + dp[v][k - x][1] - a[u] );
            ///0 2
            maxCost = max( maxCost, dp[u][x][0] + dp[v][k - x][2] );
            ///1 0
            maxCost = max( maxCost, dp[u][x][1] + dp[v][k - x][0] - a[u] );
            ///2 0
            maxCost = max( maxCost, dp[u][x][2] + dp[v][k - x][0] );
            ///1 1
            maxCost = max( maxCost, dp[u][x][1] + dp[v][k - x][1] );
            ///2 1
            maxCost = max( maxCost, dp[u][x][2] + dp[v][k - x][1] );
            ///1 2
            maxCost = max( maxCost, dp[u][x][1] + dp[v][k - x][2] );
            ///2 2
            maxCost = max( maxCost, dp[u][x][2] + dp[v][k - x][2] );
        }

        for ( int x = 1; x <= k; x++ ) {
            dp[u][x][0] = max( dp[u][x][0], max( max( dp[v][x - 1][0] + b[u] - a[u] - a[v], dp[v][x - 1][1] + b[u] - a[v] - a[u] ), dp[v][x - 1][2] + b[u] - a[u] ) );
            dp[u][x][1] = max( dp[u][x][1], max( max( dp[v][x][0], dp[v][x][1] - a[u] ), dp[v][x][2] - a[u] ) );
            dp[u][x][2] = max( dp[u][x][2], max( dp[v][x][1] - a[u], dp[v][x][2] - a[u] ) );
        }
    }

}

int main() {
    int n;

    cin >> n >> k;
    for ( int v = 1; v <= n; v++ ) {
        cin >> a[v];
        b[v] = a[v];
    }
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
        b[u] += a[v];
        b[v] += a[u];
    }

    dfs( 1, 0 );

    cout << maxCost << "\n";

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 1 ms 7000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 1 ms 7000 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 318 ms 250508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 1 ms 7000 KB Output isn't correct
5 Halted 0 ms 0 KB -