Submission #319341

#TimeUsernameProblemLanguageResultExecution timeMemory
319341caoashDostavljač (COCI18_dostavljac)C++14
14 / 140
6 ms4332 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 const int MX = 505; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; 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 vi adj[MX]; int a[MX]; int nxt[MX * MX]; int pos[MX]; ll dp[MX * MX][MX]; int fst[MX]; int n, m; vi order; void dfs(int v, int p) { for (int to : adj[v]) { if (to != p) { order.pb(to); dfs(to, v); order.pb(v); } } } 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); } order.pb(0); dfs(0, -1); assert(sz(order) <= n * n); // dbg(order); memset(pos, -1, sizeof(pos)); for (int i = 0; i <= sz(order); i++) for (int j = 0; j <= m; j++) dp[i][j] = -INF; for (int i = sz(order) - 1; i >= 0; i--) { nxt[i] = pos[order[i]]; pos[order[i]] = i; } ll ans = 0; dp[0][0] = 0; for (int i = 0; i < sz(order); i++) { if (i == pos[order[i]]) { for (int j = m - 1; j >= 0; j--) { if (dp[i][j] == -INF) continue; dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a[order[i]]); } } for (int j = 0; j <= m; j++) { if (dp[i][j] == -INF) continue; if (j + 1 <= m) dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j]); if (nxt[i] != -1) { dp[nxt[i]][j] = max(dp[nxt[i]][j], dp[i][j]); } } } for (int i = 0; i <= sz(order); i++) for (int j = 0; j <= m; j++) ans = max(ans, dp[i][j]); cout << ans << '\n'; }

Compilation message (stderr)

dostavljac.cpp:108: warning: "dbg" redefined
  108 | #define dbg(x...)
      | 
dostavljac.cpp:101: note: this is the location of the previous definition
  101 |   #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...