답안 #37056

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37056 2017-12-20T18:06:39 Z DoanPhuDuc Chase (CEOI17_chase) C++
40 / 100
4000 ms 185540 KB
#include <bits/stdc++.h>

#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n)  { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }

using namespace std;

typedef long long LL;
typedef pair <int, int> II;

const int N = 1e5 + 10;
const int A = 1e2 + 10;
const LL INFL = (LL)1e18;

int n, m;
int a[N], p[N];

LL S[N], C[N];
LL f[N][A][2];

vector <int> adj[N];

void DFS(int u, int par = -1) {
    S[u] = a[u];
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        S[u] += a[v];
        p[v] = u;
        DFS(v, u);
    }
}

void DP(int u, int par = -1) {
    f[u][0][0] = 0;
    f[u][1][1] = S[u] - a[u];
    REP(k, 0, adj[u].size()) {
        int v = adj[u][k]; if (v == par) continue;
        DP(v, u);
        FOR(i, 1, m) {
            f[u][i][0] = max(f[u][i][0], f[v][i][1] + a[u]);
            f[u][i][0] = max(f[u][i][0], f[v][i][0]);

            f[u][i][1] = max(f[u][i][1], f[v][i - 1][1] + S[u] - a[v]);
            f[u][i][1] = max(f[u][i][1], f[v][i - 1][0] + S[u] - a[v] - a[u]);
        }
    }
}

int main() {
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif // LOCAL
    scanf("%d%d", &n, &m);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n - 1) {
        int u, v; scanf("%d%d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    LL ans = -INFL;
    FOR(Root, 1, n) {
        memset(S, 0, sizeof S);
        FOR(u, 1, n)
            FOR(i, 0, m)
                FOR(k, 0, 1) f[u][i][k] = -INFL;
        DFS(Root);
        DP(Root);
        FOR(i, 0, m) ans = max(ans, max(f[Root][i][0], f[Root][i][1]));
    }
    cout << ans;
    return 0;
}

Compilation message

chase.cpp: In function 'void DFS(int, int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:29:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'void DP(int, int)':
chase.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
chase.cpp:40:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
chase.cpp: In function 'int main()':
chase.cpp:58:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
                          ^
chase.cpp:59:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
chase.cpp:61:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int u, v; scanf("%d%d", &u, &v);
                                        ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 178596 KB Output is correct
2 Correct 3 ms 178596 KB Output is correct
3 Correct 3 ms 178596 KB Output is correct
4 Correct 3 ms 178596 KB Output is correct
5 Correct 0 ms 178596 KB Output is correct
6 Correct 0 ms 178596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 178596 KB Output is correct
2 Correct 3 ms 178596 KB Output is correct
3 Correct 3 ms 178596 KB Output is correct
4 Correct 3 ms 178596 KB Output is correct
5 Correct 0 ms 178596 KB Output is correct
6 Correct 0 ms 178596 KB Output is correct
7 Correct 629 ms 178596 KB Output is correct
8 Correct 119 ms 178596 KB Output is correct
9 Correct 106 ms 178596 KB Output is correct
10 Correct 633 ms 178596 KB Output is correct
11 Correct 276 ms 178596 KB Output is correct
12 Correct 153 ms 178596 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4000 ms 185540 KB Execution timed out
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 178596 KB Output is correct
2 Correct 3 ms 178596 KB Output is correct
3 Correct 3 ms 178596 KB Output is correct
4 Correct 3 ms 178596 KB Output is correct
5 Correct 0 ms 178596 KB Output is correct
6 Correct 0 ms 178596 KB Output is correct
7 Correct 629 ms 178596 KB Output is correct
8 Correct 119 ms 178596 KB Output is correct
9 Correct 106 ms 178596 KB Output is correct
10 Correct 633 ms 178596 KB Output is correct
11 Correct 276 ms 178596 KB Output is correct
12 Correct 153 ms 178596 KB Output is correct
13 Execution timed out 4000 ms 185540 KB Execution timed out
14 Halted 0 ms 0 KB -