oj.uz

Submission #609644

# Submission time Handle Problem Language Result Execution time Memory
609644 2022-07-27T18:45:31 Z AugustinasJucas Fireworks (APIO16_fireworks) C++14
0 / 100
 4 ms 7252 KB 
#include <bits/stdc++.h>

using namespace std;
const int dydis = 3e5 + 10;
const long long inf = 1e15;
int n, m, k;
const int MX = 300;
vector<pair<int, int> > gr[dydis];

long long dp[dydis][MX+1] = {};
long long st[dydis] = {};
void dfs(int v) {
    if(gr[v].size() == 0) {
        for(auto &x : dp[v]) x = inf;
        dp[v][0] = 0;
        return ;
    }

    for(auto x : gr[v]) {
        dfs(x.first);
    }

    for(auto x : gr[v]) {
        int u = x.first; long long w = x.second;

        for(int i = 0; i <= MX; i++) st[i] = inf;


        for(int i = 0; i <= MX; i++) {
            for(int j = 0; i+j <= MX; j++) {
                st[i+j] = min(st[i+j], abs(i-w) + dp[u][j]);
            }
        }

        for(int i = 0; i <= MX; i++) {
            dp[v][i] += st[i];
        }
    }
    //cout << "dp[" << v+1 << "]:\n";
   // for(int i = 0; i <= MX; i++) {
   //     cout << i << ": " << dp[v][i] << endl;
   // }
}

int main() {
    ifstream in("in.txt");
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    in >> m >> k;
    n = m + k;
    for(int i = 1; i < n; i++) {
        int p, w;
        in >> p >> w; p--;
        gr[p].push_back({i, w});
        //gr[i].push_back({p, w});
    }

    dfs(0);

    long long ans = inf;
    for(int i = 0; i <= MX; i++) {
        ans = min(ans, dp[0][i]);
    }

    cout << ans;
    return 0;
}
/*
4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7252 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7252 KB Output is correct
2 Incorrect 4 ms 7252 KB Output isn't correct
3 Halted 0 ms 0 KB -