Submission #871647

#	Time	Username	Problem	Language	Result	Execution time	Memory
871647		vjudge1	Džumbus (COCI19_dzumbus)	C++17	20 / 110	30 ms	16732 KiB

dzumbus

//author: Ahmet Alp Orakci
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

int dp[1005][1005][2];

#define ONLINE_JUDGE
void solve() {
    fill_n(&dp[0][0][0], 1005 * 1005 * 2, -1000);

    int n, m;
    cin >> n >> m;

    vector <int> vec(n +1);
    for(int i = 1; i <= n; i++)
        cin >> vec[i];
        
    vector <int> adj[n +1];
    for(int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    
    int start = 0;
    for(int i = 1; i <= n; i++) {
        if(int(adj[i].size()) == 1) {
            start = i;
        }
    }
    
    vector <int> order;
    function <void(int, int)> dfs = [&](int node, int par) -> void {
        order.emplace_back(node);
        for(int &child : adj[node]) {
            if(child != par) 
                dfs(child, node);
        }
    };

    dfs(start, -1);
    
    for(int i = 0; i <= 1000; i++)
        dp[0][i][0] = 0;
        
    for(int i = 1; i < n; i++) {
        int u = order[i];
        for(int j = 0; j <= 1000; j++) {
            dp[i][j][0] = max(dp[i -1][j][0], dp[i -1][j][1]);

            if(j - vec[u] >= 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i -1][j - vec[u]][1] +1);
            } 
            if(j - vec[u] - vec[order[i -1]] >= 0) {
                dp[i][j][1] = max(dp[i][j][1], dp[i -1][j - vec[u] - vec[order[i -1]]][0] +2);
            }
        }
    }

    int q;
    cin >> q;

    while(q--) {
        int s;
        cin >> s;

        cout << max(dp[n -1][s][0], dp[n -1][s][1]) << "\n";
    }
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }

    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30