//modifided from tibynte's 35pts solution
#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];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
