Submission #1157497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157497		raphaelp	Constellation 3 (JOI20_constellation3)	C++20	35 / 100	517 ms	589824 KiB

constellation3

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

int main()
{
    long long N, tot = 0;
    cin >> N;
    vector<long long> Tab(N);
    vector<pair<long long, long long>> sorted;
    for (long long i = 0; i < N; i++)
    {
        cin >> Tab[i];
        sorted.push_back({Tab[i], i});
    }
    sort(sorted.begin(), sorted.end());
    long long M;
    cin >> M;
    vector<vector<pair<long long, long long>>> Stars(N);
    for (long long i = 0; i < M; i++)
    {
        long long x, y, c;
        cin >> x >> y >> c;
        x--;
        tot += c;
        Stars[x].push_back({y, c});
    }
    for (long long i = 0; i < N; i++)
        sort(Stars[i].begin(), Stars[i].end());
    vector<long long> done(N + 1), rep(N + 1), best(N + 1), score(N + 1);
    for (long long i = 0; i < N; i++)
        rep[i] = i;
    long long ans = 0;
    for (long long i = 0; i < N; i++)
    {
        long long x = sorted[i].second;
        long long left = N, right = N, leftmost = x - 1, rightmost = x + 1, limit = 1000000000;
        if (x > 0 && done[x - 1])
        {
            left = rep[x - 1];
            leftmost -= done[x - 1];
            for (long long j = 0; j < Stars[left].size(); j++)
            {
                if (Stars[left][j].first > Tab[x])
                    Stars[x].push_back(Stars[left][j]);
            }
        }
        if (x < N - 1 && done[x + 1])
        {
            right = rep[x + 1];
            rightmost += done[x + 1];
            for (long long j = 0; j < Stars[right].size(); j++)
            {
                if (Stars[right][j].first > Tab[x])
                    Stars[x].push_back(Stars[right][j]);
            }
        }
        if (leftmost >= 0)
            limit = min(limit, Tab[leftmost]);
        if (rightmost < N)
            limit = min(limit, Tab[rightmost]);
        done[leftmost + 1] = rightmost - leftmost - 1;
        done[rightmost - 1] = rightmost - leftmost - 1;
        rep[leftmost + 1] = rep[rightmost - 1] = x;
        score[x] = score[left] + score[right];
        long long low = 0, high = 0;
        for (long long j = 0; j < Stars[x].size(); j++)
        {
            if (Stars[x][j].first <= limit)
                low = max(low, Stars[x][j].second);
            else
                high = max(high, Stars[x][j].second);
        }
        for (long long j = 0; j < Stars[x].size(); j++)
            Stars[x][j].second -= low;
        best[x] = score[x] + max(low, high);
        score[x] += low;
        ans = max(ans, best[x]);
    }
    cout << tot - ans;
}

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