Submission #576187

#	Time	Username	Problem	Language	Result	Execution time	Memory
576187		erekle	Team Contest (JOI22_team)	C++17	100 / 100	223 ms	9856 KiB

team

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 27 / 27