Submission #1102414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102414		12345678	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	28 ms	24444 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=2e3+5;

ll n, m, h[nx], dp[nx][nx], x, y, c, sm, l[nx], r[nx], rt, res;
vector<pair<int, int>> d[nx];
stack<int> s;

void solve(int u)
{
    if (l[u]) solve(l[u]);
    if (r[u]) solve(r[u]);
    for (auto [y, c]:d[u]) dp[u][y]=max(dp[u][y], c+dp[l[u]][h[u]]+dp[r[u]][h[u]]);
    for (int i=h[u]; i<=n; i++) dp[u][i]=max({dp[u][i], dp[u][i-1], dp[l[u]][i]+dp[r[u]][h[u]], dp[r[u]][i]+dp[l[u]][h[u]]});
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n; i++) cin>>h[i];
    cin>>m;
    for (int i=1; i<=m; i++) cin>>x>>y>>c, d[x].push_back({y, c}), sm+=c;
    for (int i=1; i<=n; i++)
    {
        while (!s.empty()&&h[s.top()]<h[i]) l[i]=s.top(), s.pop();
        if (!s.empty()) r[s.top()]=i;
        else rt=i;
        s.push(i);
    }
    //for (int i=1; i<=n; i++) cout<<"tree "<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    solve(rt);
    for (int i=h[rt]; i<=n; i++) res=max(res, dp[rt][i]);
    cout<<sm-res;
}

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