Submission #674042

#	Time	Username	Problem	Language	Result	Execution time	Memory
674042		tibinyte	Constellation 3 (JOI20_constellation3)	C++14	35 / 100	369 ms	524288 KiB

constellation3

#include <bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        a[i] = n - a[i];
    }
    int m;
    cin >> m;
    vector<vector<pair<int, int>>> stars(n + 1);
    int sum = 0;
    for (int i = 1; i <= m; ++i)
    {
        int qui, wh, coef;
        cin >> qui >> wh >> coef;
        wh = n - wh + 1;
        sum += coef;
        stars[qui].push_back({wh, coef});
    }
    for (int i = 1; i <= n; ++i)
    {
        sort(stars[i].begin(), stars[i].end());
    }
    vector<vector<int>> g(n + 1);
    int root = 0;
    function<void(int, int, int)> build = [&](int st, int dr, int parent)
    {
        int mini = INT_MAX;
        int pos = 0;
        for (int i = st; i <= dr; ++i)
        {
            if (a[i] < mini)
            {
                mini = a[i];
                pos = i;
            }
        }
        g[parent].push_back(pos);
        g[pos].push_back(parent);
        if (!root)
        {
            root = pos;
        }
        if (pos != st)
        {
            build(st, pos - 1, pos);
        }
        if (pos != dr)
        {
            build(pos + 1, dr, pos);
        }
    };
    build(1, n, 0);
    vector<vector<int>> dp(n + 1, vector<int>(n + 2));
    function<void(int, int)> dfs = [&](int node, int parent)
    {
        int children = 0;
        vector<int> ind;
        for (auto i : g[node])
        {
            if (i != parent)
            {
                dfs(i, node);
                ind.push_back(i);
                children++;
            }
        }
        for (int j = 1; j <= n; ++j)
        {
            int cost_maxim = 0;
            for (auto k : stars[node])
            {
                if (k.first >= j)
                {
                    cost_maxim = max(cost_maxim, k.second);
                }
            }
            if (j <= a[node])
            {
                if (children == 0)
                {
                    dp[node][j] = cost_maxim;
                }
                if (children == 1)
                {
                    dp[node][j] = max(dp[ind[0]][j], dp[ind[0]][a[node] + 1] + cost_maxim);
                }
                if (children == 2)
                {

                    dp[node][j] = max({dp[ind[0]][j] + dp[ind[1]][a[node] + 1], dp[ind[0]][a[node] + 1] + dp[ind[1]][j], dp[ind[0]][a[node] + 1] + dp[ind[1]][a[node] + 1] + cost_maxim});
                }
            }
            else
            {
                for (auto k : ind)
                {
                    dp[node][j] += dp[k][j];
                }
            }
        }
    };
    dfs(root, 0);
    cout << sum - dp[root][1];
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 0 / 65