Submission #770166

#TimeUsernameProblemLanguageResultExecution timeMemory
770166PurpleCrayonConstellation 3 (JOI20_constellation3)C++17
35 / 100
1586 ms28352 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 2e5+10, MOD = 998244353; int n, m, a[N], bro[N]; int par[N]; vector<int> child[N]; vector<pair<int, ll>> can[N]; ll dp[N]; void build_tree() { memset(par, -1, sizeof(par)); vector<int> st; for (int i = 0; i < n; i++) { int last = -1; while (sz(st) && a[st.back()] < a[i]) { last = st.back(); st.pop_back(); } if (sz(st)) par[i] = st.back(); if (last != -1) par[last] = i; st.push_back(i); } } ll f(int bot, int top) { if (bot == top) return 0; return dp[bro[bot]] + f(par[bot], top); } void dfs(int c) { for (int nxt : child[c]) { dfs(nxt); } dp[c] = 0; for (int nxt : child[c]) dp[c] += dp[nxt]; for (auto [v, x] : can[c]) { ll cur = x + f(v, c); for (int nxt : child[v]) cur += dp[nxt]; dp[c] = max(dp[c], cur); } } void solve() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; build_tree(); int root = -1; for (int i = 0; i < n; i++) { if (par[i] == -1) { root = i; } } for (int i = 0; i < n; i++) if (i != root) { child[par[i]].push_back(i); } memset(bro, -1, sizeof(bro)); for (int i = 0; i < n; i++) if (i != root) { for (int nxt : child[par[i]]) if (nxt != i) { bro[i] = nxt; } } cin >> m; ll base = 0; for (int i = 0; i < m; i++) { int x, y; ll c; cin >> x >> y >> c, --x; base += c; int top = x; while (par[top] != -1 && a[par[top]] < y) top = par[top]; can[top].push_back({x, c}); } dfs(root); cout << base - dp[root] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...