Submission #1132896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132896		OI_Account	Constellation 3 (JOI20_constellation3)	C++20	14 / 100	68 ms	117060 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;


const int N = 200'000;
const int N1 = 300;
const ll INF = 1'000'000'000'000'000;

int n, m, a[N + 10], x[N + 10], y[N + 10];
ll mxCol[N1 + 10][N1 + 10], dp[N1 + 10][N1 + 10][N1 + 10];
int mx[N1 + 10][N1 + 10];
vector<pair<int, ll>> vec[N + 10];
ll sum;

void readInput() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> y[i];
        ll c;
        cin >> c;
        sum += c;
        vec[x[i]].push_back({y[i], c});
    }
}

void calcMx() {
    for (int i = 1; i <= n; i++)
        mx[i][i] = i;
    for (int len = 2; len <= n; len++)
        for (int l = 1, r = len; r <= n; l++, r++)
            if (a[r] > a[mx[l][r - 1]])
                mx[l][r] = r;
            else
                mx[l][r] = mx[l][r - 1];
}

void calcVec() {
    for (int i = 1; i <= n; i++) {
        sort(vec[i].begin(), vec[i].end());
        mxCol[i][0] = 0;
        int pnt = 0;
        for (int j = 1; j <= n; j++) {
            mxCol[i][j] = mxCol[i][j - 1];
            while (pnt < vec[i].size() && vec[i][pnt].first <= j) {
                mxCol[i][j] = max(mxCol[i][j], vec[i][pnt].second);
                pnt++;
            }
        }
    }
}

void calcDP() {
    for (int len = 1; len <= n; len++)
        for (int l = 1, r = len; r <= n; l++, r++) {
            int mid = mx[l][r];
            for (int h = 1; h <= n; h++) {
                if (h <= a[mid]) {
                    dp[l][r][h] = dp[l][mid - 1][h] + dp[mid + 1][r][h];
                    continue;
                }
                ll caseLeft = dp[l][mid - 1][h] + dp[mid + 1][r][a[mid]];
                ll caseRight = dp[l][mid - 1][a[mid]] + dp[mid + 1][r][h];
                ll caseMid = dp[l][mid - 1][a[mid]] + mxCol[mid][h] + dp[mid + 1][r][a[mid]];
                dp[l][r][h] = max({caseLeft, caseMid, caseRight});
            }
        }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcMx();
    calcVec();
    calcDP();
    cout << sum - dp[1][n][n] << flush;
    return 0;
}

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