oj.uz

Submission #143269

# Submission time Handle Problem Language Result Execution time Memory
143269 2019-08-13T13:16:04 Z Milki Chase (CEOI17_chase) C++14
0 / 100
 427 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl
#define int long long

typedef long long ll;
typedef pair<ll, ll> point;

const int MAXN = 1e5 + 5, MAXV = 105;
const ll inf = 1e16;

int n, k, val[MAXN];
vector <int> E[MAXN];
ll dp_down[MAXV][MAXN], sum[MAXN], sol, dp_up[MAXV][MAXN];

struct Best{
  point a, b;
  Best(){
    a = point(0, MAXN - 1);
    b = point(0, MAXN - 2);
  }
  void ubaci(point x){
    if(x.first > a.first){
      b = a;
      a = x;
    }
    else if(x.first > b.first){
      b = x;
    }

  }
};

Best mx1[MAXV][MAXN], mx2[MAXV][MAXN];

void dfs(int x, int p = -1){
  dp_up[1][x] = sum[x];
  mx1[1][x].ubaci( {dp_up[1][x], -1} );

  for(auto e : E[x]){
    if(e == p) continue;

    dfs(e, x);
    FOR(i, 1, k + 1){
      dp_down[i][x] = max(dp_down[i - 1][e] + sum[e] - val[x], dp_down[i][e] );
      dp_down[i][x] = max(dp_down[i][x], dp_down[i - 1][x]);

      dp_up[i][x] = max(dp_up[i][x], dp_up[i - 1][e] + sum[x] - val[e]);
      dp_up[i][x] = max(dp_up[i][x], dp_up[i][e]);
      dp_up[i][x] = max(dp_up[i][x], dp_up[i - 1][x]);

      mx1[i][x].ubaci(point(dp_up[i][x], e));
      mx2[i][x].ubaci(point(dp_down[i][x], e));
    }
  }

  REP(i, k + 1){
    if(mx1[i][x].a.second == mx2[k - i][x].a.second){
      sol = max(sol, mx1[i][x].a.first + mx2[k - i][x].b.first);
      sol = max(sol, mx1[i][x].b.first + mx2[k - i][x].a.first);
    }
    else{
      sol = max(sol, mx1[i][x].a.first + mx2[k - i][x].a.first);
      }
    }

}

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> n >> k;
  REP(i, n)
    cin >> val[i];
  REP(i, n - 1){
    int a, b; cin >> a >> b; a --; b --;
    E[a].pb(b); E[b].pb(a);
  }

  if(k == 0){
    cout << 0;
    return 0;
  }

  REP(i, n){
    for(auto e : E[i])
      sum[i] += val[e];
    sol = max(sol, sum[i]);
  }

  dfs(0);

  cout << sol;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 419 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 427 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -