oj.uz

Submission #939758

# Submission time Handle Problem Language Result Execution time Memory
939758 2024-03-06T17:42:05 Z iskhakkutbilim Chase (CEOI17_chase) C++17
70 / 100
 1573 ms 173140 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
#define int long long
 
using i64 = long long;
 
template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}
 
template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}
 
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n, k; cin >> n >> k;
    vector <int> a(n);
    for ( auto &u: a ) cin >> u;
    vector <vector<int>> G(n);
    for ( int i = 0; i + 1 < n; i++ ){
        int u, v; cin >> u >> v;
        --u, --v;
        G[u].pb(v), G[v].pb(u);
    }
    if ( !k ){ return cout << "0\n", 0; }
    const int inf = 1e15;
    auto opt = [&](int rt){
        vector <vector<ar<int,2>>> dp(n, vector <ar<int,2>> (k + 1, {-inf, -inf}));
        vector <int> s(n);
        auto dfs2 = [&](auto dfs2, int u, int p) -> void{
			for ( auto &v: G[u] ){
				if ( v != p ){
					s[u] += a[v];
					dfs2(dfs2, v, u);
				}
			}
		};
		dfs2(dfs2, rt, -1);
        auto dfs = [&](auto dfs, int u, int p) -> void{
            for ( auto &v: G[u] ){
                if ( v == p ) continue;
                for ( int j = 0; j <= k; j++ ){
                    for ( auto t: {0, 1} ){
                        if ( j - t < 0 ) continue;
                        for ( auto f: {0, 1} ){
                            chmax(dp[v][j][t], dp[u][j - t][f] + s[v] * t);
                        }
                    }
                }
                dfs(dfs, v, u);
            }
        };
        dp[rt][1][1] = s[rt];
        dfs(dfs, rt, -1);
        int ret = 0;
        for ( int i = 0; i < n; i++ ){
            for ( int j = 0; j <= k; j++ ){
                for ( auto f: {0, 1} ){
                    chmax(ret, dp[i][j][f]);
                }
            }
        }
        return ret;
    };
    int ans = 0;
    for ( int i = 0; i < n; i++ ){
        chmax(ans, opt(i));
        if ( n > 1e3 ) break;
    }
    cout << ans;
 
    cout << '\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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 388 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 388 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 1503 ms 2640 KB Output is correct
8 Correct 107 ms 604 KB Output is correct
9 Correct 91 ms 600 KB Output is correct
10 Correct 1573 ms 2464 KB Output is correct
11 Correct 521 ms 1056 KB Output is correct
12 Correct 178 ms 720 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 172992 KB Output is correct
2 Correct 236 ms 173140 KB Output is correct
3 Correct 183 ms 170184 KB Output is correct
4 Correct 49 ms 14936 KB Output is correct
5 Correct 255 ms 168784 KB Output is correct
6 Correct 252 ms 170008 KB Output is correct
7 Correct 265 ms 170144 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 388 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 1503 ms 2640 KB Output is correct
8 Correct 107 ms 604 KB Output is correct
9 Correct 91 ms 600 KB Output is correct
10 Correct 1573 ms 2464 KB Output is correct
11 Correct 521 ms 1056 KB Output is correct
12 Correct 178 ms 720 KB Output is correct
13 Correct 235 ms 172992 KB Output is correct
14 Correct 236 ms 173140 KB Output is correct
15 Correct 183 ms 170184 KB Output is correct
16 Correct 49 ms 14936 KB Output is correct
17 Correct 255 ms 168784 KB Output is correct
18 Correct 252 ms 170008 KB Output is correct
19 Correct 265 ms 170144 KB Output is correct
20 Incorrect 263 ms 170020 KB Output isn't correct
21 Halted 0 ms 0 KB -