oj.uz

Submission #321161

# Submission time Handle Problem Language Result Execution time Memory
321161 2020-11-11T09:08:41 Z armaho Dostavljač (COCI18_dostavljac) C++14
140 / 140
 310 ms 2532 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 748 KB Output is correct
2 Correct 4 ms 876 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 932 KB Output is correct
2 Correct 45 ms 1124 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 1156 KB Output is correct
2 Correct 26 ms 1132 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1516 KB Output is correct
2 Correct 188 ms 1608 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 2020 KB Output is correct
2 Correct 63 ms 1892 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 2532 KB Output is correct
2 Correct 31 ms 2404 KB Output is correct