oj.uz

Submission #197764

# Submission time Handle Problem Language Result Execution time Memory
197764 2020-01-22T21:23:57 Z heon Dostavljač (COCI18_dostavljac) C++17
14 / 140
 1840 ms 60428 KB 
#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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 60280 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 60252 KB Output isn't correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 60200 KB Output isn't correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 60252 KB Output isn't correct

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 97 ms 60296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 60252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 508 ms 60292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 60280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 980 ms 60384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1840 ms 60428 KB Output isn't correct
2 Halted 0 ms 0 KB -