Submission #1175312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175312		VMaksimoski008	Constellation 3 (JOI20_constellation3)	C++20	35 / 100	53 ms	42404 KiB

constellation3

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int maxn = 1e5 + 5;

ll dp[2005][2005];
int n, m, c[maxn], L[maxn], R[maxn], T[maxn][20];
vector<pii> S[maxn];

int mrg(int i, int j) {
    return c[i] < c[j] ? i : j;
}

int query(int l, int r) {
    int k = __lg(r - l + 1);
    return mrg(T[l][k], T[r-(1<<k)+1][k]);
}

void dnc(int l, int r, int prv = 0) {
    if(l > r) return ;
    int p = query(l, r);
    if(p < prv) L[prv] = p;
    if(prv < p) R[prv] = p;
    dnc(l, p-1, p);
    dnc(p+1, r, p);
}

ll f(int r, int mn) {
    if(!r) return 0;
    if(dp[r][mn] != -1) return dp[r][mn];

    ll ans = 0;

    for(auto [y, w] : S[r])
        if(y >= mn)
            ans = max(ans, (ll)w + f(L[r], c[r]+1) + f(R[r], c[r]+1));
    ans = max(ans, f(L[r], mn) + f(R[r], c[r]+1));
    ans = max(ans, f(L[r], c[r]+1) + f(R[r], mn));

    return dp[r][mn] = ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n;
    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=n; i++) {
        cin >> c[i], c[i] = n - c[i];
        T[i][0] = i;
    }

    for(int j=1; j<20; j++)
        for(int i=1; i+(1<<j)-1<=n; i++) T[i][j] = mrg(T[i][j-1], T[i+(1<<(j-1))][j-1]);

    dnc(1, n);

    cin >> m;
    ll sum = 0;
    for(int i=1; i<=m; i++) {
        int x, y, w; cin >> x >> y >> w;
        y = n - y + 1; sum += w;
        S[x].push_back({ y, w });
    }

    int p = query(1, n);
    cout << sum - f(p, 0) << '\n';
}

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