oj.uz

Submission #35824

# Submission time Handle Problem Language Result Execution time Memory
35824 2017-12-01T05:09:50 Z funcsr Chase (CEOI17_chase) C++14
70 / 100
 383 ms 93064 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
inline void chmax(long long &x, long long v) { if (x < v) x = v; }

int N, K;
int A[100001];
long long T[100000];
vector<int> G[100000];

long long dp[100000][101];
void f(int x, int p) {
  for (int t : G[x]) {
    if (t == p) continue;
    f(t, x);
    rep(k, K+1) chmax(dp[x][k], dp[t][k]);
    rep(k, K) chmax(dp[x][k+1], dp[t][k]+T[x]-A[p]);
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N >> K;
  rep(i, N) cin >> A[i];
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[u].pb(v);
    G[v].pb(u);
  }
  rep(i, N) for (int t : G[i]) T[i] += A[t];

  long long m = 0;
  rep(i, N) {
    if (N > 1000 && i > 0) continue;
    rep(i, N) rep(j, K+1) dp[i][j] = 0;
    f(i, N);
    m = max(m, dp[i][K]);
  }
  cout << m << "\n";
  return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 84596 KB Output is correct
2 Correct 0 ms 84596 KB Output is correct
3 Correct 0 ms 84596 KB Output is correct
4 Correct 0 ms 84596 KB Output is correct
5 Correct 0 ms 84596 KB Output is correct
6 Correct 0 ms 84596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 84596 KB Output is correct
2 Correct 0 ms 84596 KB Output is correct
3 Correct 0 ms 84596 KB Output is correct
4 Correct 0 ms 84596 KB Output is correct
5 Correct 0 ms 84596 KB Output is correct
6 Correct 0 ms 84596 KB Output is correct
7 Correct 369 ms 84596 KB Output is correct
8 Correct 49 ms 84596 KB Output is correct
9 Correct 36 ms 84596 KB Output is correct
10 Correct 383 ms 84596 KB Output is correct
11 Correct 143 ms 84596 KB Output is correct
12 Correct 59 ms 84596 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 93064 KB Output is correct
2 Correct 156 ms 93036 KB Output is correct
3 Correct 79 ms 88148 KB Output is correct
4 Correct 89 ms 87764 KB Output is correct
5 Correct 176 ms 87764 KB Output is correct
6 Correct 179 ms 87764 KB Output is correct
7 Correct 179 ms 87764 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 84596 KB Output is correct
2 Correct 0 ms 84596 KB Output is correct
3 Correct 0 ms 84596 KB Output is correct
4 Correct 0 ms 84596 KB Output is correct
5 Correct 0 ms 84596 KB Output is correct
6 Correct 0 ms 84596 KB Output is correct
7 Correct 369 ms 84596 KB Output is correct
8 Correct 49 ms 84596 KB Output is correct
9 Correct 36 ms 84596 KB Output is correct
10 Correct 383 ms 84596 KB Output is correct
11 Correct 143 ms 84596 KB Output is correct
12 Correct 59 ms 84596 KB Output is correct
13 Correct 146 ms 93064 KB Output is correct
14 Correct 156 ms 93036 KB Output is correct
15 Correct 79 ms 88148 KB Output is correct
16 Correct 89 ms 87764 KB Output is correct
17 Correct 176 ms 87764 KB Output is correct
18 Correct 179 ms 87764 KB Output is correct
19 Correct 179 ms 87764 KB Output is correct
20 Incorrect 176 ms 87764 KB Output isn't correct
21 Halted 0 ms 0 KB -