Submission #197764

#	Time	Username	Problem	Language	Result	Execution time	Memory
197764		heon	Dostavljač (COCI18_dostavljac)	C++17	14 / 140	1840 ms	60428 KiB

dostavljac

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <iomanip>
using namespace std;
#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;
int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }
int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
int ctz(int x) { return __builtin_ctz(x); }
int clz(int x) { return __builtin_clz(x); }

vi g[505];
int dp[505][505][30][2];
int a[505];

int dfs(int u, int m, int c, int took, int p){
  if(m < 0) return -mod;
  if(c == min(30, int(g[u].size()))){
    if(m && !took) return a[u];
    return 0;
  }
  int& ret = dp[u][m][c][took];
  if(ret != -1) return ret;
  ret = 0;
  if(g[u][c] == p) return ret = dfs(u, m, c + 1, took, p);
  if(!took) ret = max(ret, a[u] + dfs(u, m - 1, c, 1, p));
  ret = max(ret, dfs(g[u][c], m - 1, 0, 0, u));
  ret = max(ret, dfs(u, m, c + 1, took, p));
  for(int i = 0; i <= m - 2; i++){
    ret = max(ret, dfs(g[u][c], i, 0, 0, u) + dfs(u, m - 2 - i, c + 1, took, p));
  }
  return ret;
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);
  #ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif

  int n, t;
  cin >> n >> t;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  for(int i = 0; i < n - 1; i++){
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  memset(dp, -1, sizeof dp);
  cout << dfs(1, t, 0, 0, 1);
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14