Submission #83397

#TimeUsernameProblemLanguageResultExecution timeMemory
83397charlies_mooDostavljač (COCI18_dostavljac)C++17
140 / 140
206 ms804 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]; memset(ret.dp1, 0, sizeof(int) * (m+1)); memset(ret.dp2, 0, sizeof(int) * (m+1)); ret.dp1[1] = ret.dp2[1] = a[x]; 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.dp2[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; } 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); } node ret = dfs(e, a, 0, -1, m); int ans = 0; for (int i = 0; i <= m; i++) { ans = max(ans, ret.dp2[i]); } printf("%d\n", ans); return 0; }

Compilation message (stderr)

dostavljac.cpp: In function 'node dfs(vi*, int*, int, int, int)':
dostavljac.cpp:21: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:46: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:49:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
dostavljac.cpp:54: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...