Submission #321161

#	Time	Username	Problem	Language	Result	Execution time	Memory
321161		armaho	Dostavljač (COCI18_dostavljac)	C++14	140 / 140	310 ms	2532 KiB

dostavljac

#include <iostream>
#include <vector>

using namespace std;

template <typename input_type>
input_type get() {
    input_type input;
    cin >> input;

    return input;
}

const int max_num = (5e2 + 5), max_tmp = 2;
int sz, tm, ppr[max_num], dp[max_tmp][max_num][max_num];
vector <int> nghbr[max_num];

void DFS(int vrtx, int prnt) {
    for (int i = 1; i < (tm + 1); i++) {
        dp[0][vrtx][i] = ppr[vrtx];
        dp[1][vrtx][i] = ppr[vrtx];
    }

    for (int ngh: nghbr[vrtx]) {
        if (ngh != prnt) {
            DFS(ngh, vrtx);

            for (int i = tm; i > 0; i--) {
                for (int j = 0; j < i; j++) {
                    dp[0][vrtx][i] = max(dp[0][vrtx][i], (max(dp[0][ngh][j], dp[1][ngh][j]) + dp[1][vrtx][i - j - 1]));

                    if (j != (i - 1)) {
                        dp[0][vrtx][i] = max(dp[0][vrtx][i], dp[1][ngh][j] + dp[0][vrtx][i - j - 2]);
                        dp[1][vrtx][i] = max(dp[1][vrtx][i], dp[1][ngh][j] + dp[1][vrtx][i - j - 2]);
                    }
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    sz = get<int>(); tm = get<int>();
    for (int i = 1; i < (sz + 1); i++) {
        ppr[i] = get<int>();
    }
    for (int i = 0; i < (sz - 1); i++) {
        pair <int, int> endpnt = {get<int>(), get<int>()};

        nghbr[endpnt.first].push_back(endpnt.second);
        nghbr[endpnt.second].push_back(endpnt.first);
    }

    DFS(1, 0);

    cout << max(dp[0][1][tm], dp[1][1][tm]);
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14