Submission #319367

#TimeUsernameProblemLanguageResultExecution timeMemory
319367caoashDostavljač (COCI18_dostavljac)C++14
140 / 140
412 ms2412 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define lb lower_bound #define ub upper_bound using pi = pair<int,int>; #define f first #define s second #define mp make_pair namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef mikey using namespace output; #else using namespace output; #define dbg(x...) #endif const int MX = 505; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; int n, m; vi adj[MX]; int a[MX]; int dp[MX][MX][2]; void dfs(int v, int p) { vi child; for (int to : adj[v]) { if (to != p) { dfs(to, v); child.pb(to); } } int dp_pre[sz(child) + 1][m + 1][2]; memset(dp_pre, -0x3f3f3f, sizeof(dp_pre)); dp_pre[0][0][0] = 0; for (int i = 1; i <= sz(child); i++) { int to = child[i - 1]; for (int j = 0; j <= m; j++) { for (int cj = 0; cj <= j; cj++) { if (j - cj - 2 >= 0) { dp_pre[i][j][0] = max(dp_pre[i][j][0], dp_pre[i - 1][j - cj - 2][0] + dp[to][cj][0]); dp_pre[i][j][1] = max(dp_pre[i][j][1], dp_pre[i - 1][j - cj - 2][1] + dp[to][cj][0]); } if (j - cj - 1 >= 0) { dp_pre[i][j][1] = max(dp_pre[i][j][1], dp_pre[i - 1][j - cj - 1][0] + dp[to][cj][0]); dp_pre[i][j][1] = max(dp_pre[i][j][1], dp_pre[i - 1][j - cj - 1][0] + dp[to][cj][1]); } } dp_pre[i][j][0] = max(dp_pre[i][j][0], dp_pre[i - 1][j][0]); dp_pre[i][j][1] = max(dp_pre[i][j][1], dp_pre[i - 1][j][1]); // if (v == 0) dbg(i, j, dp_pre[i][j][0], dp_pre[i][j][1]); } } for (int i = 0; i <= m; i++) { dp[v][i][0] = dp_pre[sz(child)][i][0]; dp[v][i][1] = dp_pre[sz(child)][i][1]; } for (int i = m - 1; i >= 0; i--) { dp[v][i + 1][0] = max(dp[v][i + 1][0], dp[v][i][0] + a[v]); dp[v][i + 1][1] = max(dp[v][i + 1][1], dp[v][i][1] + a[v]); } // for (int i = 0; i <= m; i++) dbg(v, i, dp[v][i][0], dp[v][i][1]); } int main(){ /* #ifdef mikey freopen("a.in", "r", stdin); #endif */ ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--, v--; adj[u].pb(v), adj[v].pb(u); } dfs(0, -1); cout << max(dp[0][m][0], dp[0][m][1]) << '\n'; }

Compilation message (stderr)

dostavljac.cpp:104: warning: "dbg" redefined
  104 | #define dbg(x...)
      | 
dostavljac.cpp:97: note: this is the location of the previous definition
   97 |   #define dbg(x...) pr("[", #x, "] = ["), pc(x);
      |
#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...