oj.uz

Submission #234096

# Submission time Handle Problem Language Result Execution time Memory
234096 2020-05-23T04:52:24 Z Fischer Dostavljač (COCI18_dostavljac) C++14
140 / 140
 9 ms 2432 KB 
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author Miguel Mini
 */

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define trav(v, x) for (auto v : x)
#define re(x, y, z) for (int x=y; x<z; ++x)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set_to(x, v) fill(all(x), v)
#define eb emplace_back
#define lso(x) ((x)&-(x))
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
const int mod = 1e9 + 7;
const int maxn = 505;
int A[maxn];
int n, m;
vi g[maxn];
int dp[maxn][maxn][2];
int sz[maxn];

int dfs(int x, int p) {
    sz[x] = 1;
    dp[x][0][0] = dp[x][0][1] = 0;
    dp[x][1][0] = dp[x][1][1] = A[x];
    trav(v, g[x]) {
        if (v == p) continue;
        dfs(v, x);
        sz[x] += sz[v];
        for (int i = min(m, 3 * sz[x] - 2); i >= 1; --i) {
            for (int j = min(i, 3 * sz[v]); j >= max(1, i - 3 * (sz[x] - sz[v])); --j) {
                dp[x][i][0] = max(dp[x][i][0], dp[x][i - j][1] + dp[v][j - 1][0]);
                if (j >= 2) {
                    dp[x][i][0] = max(dp[x][i][0], dp[x][i - j][0] + dp[v][j - 2][1]);
                    dp[x][i][1] = max(dp[x][i][1], dp[x][i - j][1] + dp[v][j - 2][1]);
                }
            }
        }
    }
}

class COC_18_dostavljac {
public:
    void solveOne(istream& in, ostream& out) {
        in >> n >> m;
        m = min(m, 3*n - 2);
        re(i, 1, n + 1) {
            in >> A[i];
        }
        memset(dp, 0, sizeof dp);
        re(i, 1, n+1) g[i].clear();
        re(i, 1, n) {
            int a, b;
            in >> a >> b;
            g[a].eb(b);
            g[b].eb(a);
        }
        dfs(1, 0);
        int ans = 0;
        for (int i = 0; i <= m; ++i) {
            ans = max(ans, dp[1][i][0]);
        }
        out << ans << endl;
    }

    void solve(istream& in, ostream& out) {
        int testNumber = 1;
        //in >> testNumber;
        re(tc, 1, testNumber+1) {
            //out << "Case #" << tc << ": ";
            solveOne(in, out);
        }
    }
};


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	COC_18_dostavljac solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Compilation message

dostavljac.cpp: In function 'int dfs(int, int)':
dostavljac.cpp:46:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2432 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2432 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2432 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2304 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2304 KB Output is correct
2 Correct 7 ms 2432 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2432 KB Output is correct
2 Correct 7 ms 2304 KB Output is correct