Submission #83361

#TimeUsernameProblemLanguageResultExecution timeMemory
83361charlies_mooDostavljač (COCI18_dostavljac)C++17
14 / 140
194 ms732 KiB
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; typedef vector<int> vi; typedef struct { int *dp1, *dp2; } node; node dfs(vi e[], int a[], int x, int p, int m) { node ret; ret.dp1 = new int[m+1]; ret.dp2 = new int[m+1]; for (int i = 1; i <= m; i++) { ret.dp1[i] = ret.dp2[i] = a[x]; } ret.dp1[0] = ret.dp2[0] = 0; for (int i = 0; i < e[x].size(); i++) { if (e[x][i] == p) { continue; } node t = dfs(e, a, e[x][i], x, m); for (int j = m; j >= 0; j--) { for (int k = 0; k <= j - 1; k++) { if (j - k - 2 >= 0) { ret.dp1[j] = max(ret.dp1[j], ret.dp1[j-k-2] + t.dp1[k]); } ret.dp2[j] = max(ret.dp2[j], ret.dp1[j-k-1] + t.dp2[k]); } } delete[] t.dp1; delete[] t.dp2; } // printf("%d:\n", x); // for (int i = 0; i <= m; i++) { // printf("%d %d %d\n", i, ret.dp1[i], ret.dp2[i]); // } return ret; } int main() { int n, m; scanf("%d %d", &n, &m); int a[n]; for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } vi e[n]; for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); u--, v--; e[u].push_back(v); e[v].push_back(u); } printf("%d\n", dfs(e, a, 0, -1, m).dp2[m]); return 0; }

Compilation message (stderr)

dostavljac.cpp: In function 'node dfs(vi*, int*, int, int, int)':
dostavljac.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < e[x].size(); i++) {
                     ~~^~~~~~~~~~~~~
dostavljac.cpp: In function 'int main()':
dostavljac.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
dostavljac.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
dostavljac.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...