oj.uz

Submission #424606

# Submission time Handle Problem Language Result Execution time Memory
424606 2021-06-12T07:35:30 Z blue Magic Tree (CEOI19_magictree) C++17
34 / 100
 573 ms 1048580 KB 
#include <iostream>
#include <vector>
using namespace std;

/*
Let dp[u][d] be the maximum amount of juice that can be collected if the edge (u, p[u]) is cut on day d.
Let dp'[u][d] = max{d1 <= d | dp[u][d]}

dp[u][d] = (d == fruit_day[u]) * fruit_weight[u]
           + sum{v in children[u] | dp'[v][d]}

dp'[u][d] = max(dp'[u][d-1], dp[u][d])
*/

int main()
{
    int n, m, k;
    cin >> n >> m >> k;

    vector<int> children[n+1];
    for(int i = 2; i <= n; i++)
    {
        int p;
        cin >> p;
        children[p].push_back(i);
    }

    vector<int> fruit_day(n+1, 1);
    vector<long long> fruit_weight(n+1, 0);
    for(int f = 1; f <= m; f++)
    {
        int v, d, w;
        cin >> v >> d >> w;
        fruit_day[v] = d;
        fruit_weight[v] = w;
    }

    vector< vector<long long> > dp(n+1, vector<long long>(k+1, 0));
    vector< vector<long long> > dp1(n+1, vector<long long>(k+1, 0));
    for(int u = n; u >= 1; u--)
    {
        dp[u][0] = 0;
        dp1[u][0] = 0;
        for(int d = 1; d <= k; d++)
        {
            dp[u][d] = (d == fruit_day[u]) * fruit_weight[u];
            for(int v: children[u])
                dp[u][d] += dp1[v][d];

            dp1[u][d] = max(dp[u][d], dp1[u][d-1]);
        }
    }

    cout << dp1[1][k] << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 545 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 16076 KB Output is correct
2 Correct 17 ms 16068 KB Output is correct
3 Correct 14 ms 16012 KB Output is correct
4 Runtime error 573 ms 1048580 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 18500 KB Output is correct
2 Correct 153 ms 18412 KB Output is correct
3 Correct 159 ms 19328 KB Output is correct
4 Correct 127 ms 16856 KB Output is correct
5 Correct 141 ms 19980 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 178 ms 46040 KB Output is correct
11 Correct 148 ms 30252 KB Output is correct
12 Correct 154 ms 46936 KB Output is correct
13 Correct 143 ms 44452 KB Output is correct
14 Correct 145 ms 47476 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 448 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 17 ms 16076 KB Output is correct
11 Correct 17 ms 16068 KB Output is correct
12 Correct 14 ms 16012 KB Output is correct
13 Runtime error 573 ms 1048580 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Runtime error 545 ms 1048580 KB Execution killed with signal 9
11 Halted 0 ms 0 KB -