Submission #83392

#TimeUsernameProblemLanguageResultExecution timeMemory
83392charlies_mooDostavljač (COCI18_dostavljac)C++17
140 / 140
332 ms2652 KiB
#include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; const int N = 500; const int M = 500; typedef vector<int> vi; int dp1[N][M+1], dp2[N][M+1]; void dfs(vi e[], int a[], int x, int p, int m) { for (int i = 1; i <= m; i++) { dp1[x][i] = dp2[x][i] = a[x]; } for (int i = 0; i < e[x].size(); i++) { if (e[x][i] == p) { continue; } 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) { dp1[x][j] = max(dp1[x][j], dp1[x][j-k-2] + dp1[e[x][i]][k]); dp2[x][j] = max(dp2[x][j], dp2[x][j-k-2] + dp1[e[x][i]][k]); } dp2[x][j] = max(dp2[x][j], dp1[x][j-k-1] + dp2[e[x][i]][k]); } } } // printf("%d:\n", x); // for (int i = 0; i <= m; i++) { // printf("%d %d %d\n", i, dp1[x][i], dp2[x][i]); // } } 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); } dfs(e, a, 0, -1, m); printf("%d\n", dp2[0][m]); return 0; }

Compilation message (stderr)

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