Submission #795236

#	Time	Username	Problem	Language	Result	Execution time	Memory
795236		vjudge1	Team Contest (JOI22_team)	C++17	64 / 100	195 ms	13136 KiB

team

#include<bits/stdc++.h>

using namespace std;


struct person {
    int x, y, z;
};

const int N = 150000;

int w[300 + 10][300 + 10];

void add(int A, int B) {
    w[A][B] = max(w[A][B], A + B);
}
void build() {
    for(int i = 300; i >= 0; i--) {
        for(int j = 300; j >= 0; j--) {
            w[i][j] = max({w[i][j + 1], w[i + 1][j], w[i][j]});
        }
    }
}

vector<pair<int, int>> pnts[N + 10];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<person> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    if(n <= 4000) {
        sort(a.begin(), a.end(), [](person l, person r) {return l.z < r.z;});
        int ans = 0;
        for(int i = 0; i < n; i++) {
            // cout << a[i].x << ' ' << a[i].y << ' ' << a[i].z << '\n';
            int Y = 0, l = i + 1;
            for(int j = i + 1; j < n; j++) {
                if(a[j].x >= a[i].x || a[j].z == a[i].z) continue;
                while (a[l].z < a[j].z) {
                    if(a[l].x < a[i].x) Y = max(Y, a[l].y);
                    l++;
                }

                if(Y > max(a[i].y, a[j].y)) {
                    ans = max(ans, a[i].x + Y + a[j].z);
                }
            }
            int X = 0, r = i + 1;
            for(int j = i + 1; j < n; j++) {
                if(a[j].y >= a[i].y || a[j].z == a[i].z) continue;
                while (a[r].z < a[j].z) {
                    if(a[r].y < a[i].y) X = max(X, a[r].x);
                    r++;
                }

                if(X > max(a[i].x, a[j].x)) {
                    ans = max(ans, a[i].y + X + a[j].z);
                }
            }

        }
        if(ans == 0) ans = -1;
        cout << ans;
        return 0;
    }
    sort(a.begin(), a.end(), [](person l, person r) {return l.x < r.x;});
    
    int mxZ[300 + 10] = {}, mxY[300 + 10] = {};
    for(int i = 0; i < n; i++) {
        mxY[a[i].z] = max(mxY[a[i].z], a[i].y);
        mxZ[a[i].y] = max(mxZ[a[i].y], a[i].z);
        for(int j = a[i].z + 1; j <= 300; j++) 
            mxY[j] = max(mxY[j], mxY[j - 1]);
        for(int j = a[i].y + 1; j <= 300; j++) 
            mxZ[j] = max(mxZ[j], mxZ[j - 1]);
        if(mxZ[a[i].y - 1] > a[i].z) 
            pnts[i].push_back({a[i].y, mxZ[a[i].y - 1]});
        if(mxY[a[i].z - 1] > a[i].y) 
            pnts[i].push_back({mxY[a[i].z - 1], a[i].z});
    }
    int res = 0;
    int l = 0;
    for(int i = 0; i < n; i++) {
        while(a[l].x < a[i].x) {
            for(auto [A, B] : pnts[l]) {
                add(A, B);
            }
            l++;
        }
        if(i && a[i].x != a[i - 1].x) build();
        if(w[a[i].y + 1][a[i].z + 1]) 
            res = max(a[i].x + w[a[i].y + 1][a[i].z + 1], res);
    }
    if(res == 0) cout << -1;
    else cout << res;
}

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