Submission #222008

#TimeUsernameProblemLanguageResultExecution timeMemory
222008ZwariowanyMarcinDostavljač (COCI18_dostavljac)C++14
98 / 140
2092 ms2680 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair #define ss(x) (int) x.size() #define sz(x) (int) x.size() #define fi first #define se second #define cat(x) cerr << #x << " = " << x << endl #define rep(i, j, n) for (int i = j; i <= n; ++i) #define per(i, j, n) for (int i = n; j <= i; --i) #define all(x) x.begin(), x.end() #define cint int& using namespace std; const int nax = 505; void maxi(int &a, int b) { a = max(a, b); } int n, m; int a, b; int cost[nax]; vector <int> g[nax]; int dp[nax][nax][2][2]; int dp2[nax][2][2]; // 0 to musze wrocic -> 0 // 1 to nie musze -> 0 / 1 void dfs(int v, int p) { rep(i, 0, m) rep(a, 0, 1) rep(b, 0, 1) dp[v][i][a][b] = -1e9; dp[v][0][0][0] = 0; dp[v][0][1][0] = 0; dp[v][1][0][0] = cost[v]; dp[v][1][1][0] = cost[v]; for (auto it : g[v]) { if (it == p) continue; dfs(it, v); rep(i, 0, m) rep(a, 0, 1) rep(b, 0, 1) dp2[i][a][b] = dp[v][i][a][b]; rep(i, 0, m) rep(j, 0, m) rep(a, 0, 1) rep(b, 0, 1) rep(c, 0, 1) rep(d, 0, 1) { if (a == 0 && b == 1) continue; if (c == 0 && d == 1) continue; if (a == 0 && c == 1) continue; if (a == 1 && b == 1 && c == 1) continue; if (a == 0 && c == 0) { int s = i + j + 2; if (s <= m) maxi(dp2[s][0][0], dp[v][i][a][b] + dp[it][j][c][d]); } if (a == 1) { int e = (b | c); int s = i + j + 1 + !(c == 1); if (s <= m) maxi(dp2[s][1][e], dp[v][i][a][b] + dp[it][j][c][d]); } } rep(i, 0, m) rep(a, 0, 1) rep(b, 0, 1) dp[v][i][a][b] = dp2[i][a][b]; } } int main() { scanf ("%d%d", &n, &m); rep(i, 1, n) scanf ("%d", cost + i); rep(i, 1, n - 1) { scanf ("%d%d", &a, &b); g[a].pb(b); g[b].pb(a); } dfs(1, 0); int res = 0; rep(i, 0, m) rep(a, 0, 1) rep(b, 0, 1) maxi(res, dp[1][i][a][b]); printf ("%d\n", res); return 0; }

Compilation message (stderr)

dostavljac.cpp: In function 'int main()':
dostavljac.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf ("%d%d", &n, &m);
  ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:83:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", cost + i);
               ~~~~~~^~~~~~~~~~~~~~~~
dostavljac.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a, &b);
   ~~~~~~^~~~~~~~~~~~~~~~
#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...