Submission #409575

#	Time	Username	Problem	Language	Result	Execution time	Memory
409575		tengiz05	Fireworks (APIO16_fireworks)	C++17	19 / 100	32 ms	696 KiB

fireworks

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 305;
int n, m;
std::vector<std::pair<int, int>> e[N];
int dp[N][N];
void dfs(int u){
    if (e[u].empty()) {
        dp[u][0] = 0;
        return;
    }
    for (auto [v, w] : e[u]) {
        dfs(v);
    }
    for (int i = 0; i < N; i++) {
        dp[u][i] = 0;
        for (auto [v, w] : e[u]) {
            int ans = 1e9;
            for (int t = 0; t <= i; t++) {
                ans = std::min(ans, abs(w - t) + dp[v][i - t]);
            }
            dp[u][i] += ans;
            dp[u][i] = std::min(dp[u][i], int(1e9));
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m;
    for (int i = 1; i < n + m; i++) {
        int p, w;
        std::cin >> p >> w;
        p--;
        e[p].emplace_back(i, w);
    }
    memset(dp, 0x3f, sizeof dp);
    dfs(0);
    int ans = 1e9;
    for (int i = 0; i < N; i++) {
        ans = std::min(ans, dp[0][i]);
    }
    std::cout << ans << '\n';
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 19 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45