Submission #576187

#TimeUsernameProblemLanguageResultExecution timeMemory
576187erekleTeam Contest (JOI22_team)C++17
100 / 100
223 ms9856 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>

using namespace std;

int main() {
    int n; cin >> n;
    vector<int> x(n), y(n), z(n);
    for (int i = 0; i < n; ++i) cin >> x[i] >> y[i] >> z[i];
    
    vector<int> byX(n);
    for (int i = 0; i < n; ++i) byX[i] = i;
    sort(byX.begin(), byX.end(), [&x](int i, int j){return x[i]>x[j];});

    priority_queue<pair<int, int>> byY, byZ;
    for (int i = 0; i < n; ++i) {
        byY.emplace(y[i], i);
        byZ.emplace(z[i], i);
    }

    int bestTeam = -1;
    for (int i : byX) {
        while (!byY.empty() && !byZ.empty()) {
            if (x[byY.top().second] >= x[i]) byY.pop();
            else if (x[byZ.top().second] >= x[i]) byZ.pop();
            else if (z[byY.top().second] >= byZ.top().first) byY.pop();
            else if (y[byZ.top().second] >= byY.top().first) byZ.pop();
            /* For the two lines above, >= is necessary rather than simply ==
            This is because a beaver may have been deleted from byZ since it was both y-maximal and z-maximal
            but not from byY, since we do not find and delete these double maximal beavers from the other pq.
            This means the z value of a beaver in byY may be greater than the largest z value in byZ.
            The same applies to the y values of beavers in byZ.
            */
            else break;
        }
        if (!byY.empty() && !byZ.empty()) {
            int j = byY.top().second, k = byZ.top().second;
            assert(y[j] > y[k]); assert(z[k] > z[j]);
            int Y = byY.top().first, Z = byZ.top().first;
            if (Y > y[i] && Z > z[i]) bestTeam = max(bestTeam, x[i] + Y + Z);
        }
    }
    cout << bestTeam << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...