Submission #1138189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138189		fzyzzz_z	Team Contest (JOI22_team)	C++20	46 / 100	32 ms	1548 KiB

team

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

using ll = long long;

void print(array<int,3> v) {
    cout << v[0] << ' ' << v[1] << ' ' << v[2] << '\n'; 
}
void clean(vector<array<int, 3>> & v) {
    vector<array<int, 3>> res; 
    int n = v.size(); 
    vector<int> yes(n, 1); 
    for (int t = 0; t < 3; ++t) {
        map<vector<int>, vector<int>> f; 
        for (int i = 0; i < n; ++i) {
            vector<int> x, y; 
            for (int j = 0; j < 3; ++j) {
                if (j == t) y.push_back(v[i][j]); 
                else x.push_back(v[i][j]); 
            }
            f[x].push_back(y[0]); 
        }
        for (auto & [x, y]: f) sort(y.begin(), y.end()); 
        for (int i = 0; i < n; ++i) {
            vector<int> x; 
            for (int j = 0; j < 3; ++j) {
                if (j != t) x.push_back(v[i][j]); 
            }
            if (v[i][t] != f[x][0] && v[i][t] != f[x].back()) {
                yes[i] = 0; 
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (yes[i]) {
            res.push_back(v[i]); 
            // cout << v[i][0] << ' ' << v[i][1] << ' ' << v[i][2] << '\n'; 
        }
    }
    v = res; 
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; 
    cin >> n; 
    map<int, vector<pair<int, int>>> f; 
    set<array<int, 3>> seen; 
    vector<array<int, 3>> v; 
    for (int i = 0; i < n; ++i) {
        int x, y, z; 
        cin >> x >> y >> z; 
        if (seen.find({x, y, z}) != seen.end()) continue; 
        seen.insert({x, y, z}); 
        v.push_back({x, y, z}); 
    }

     n = v.size(); 
    if (n <= 2000) {
        clean(v); 

        if (n <= 100) {
            n = v.size(); 
            int ans = -1; 
            for (int i = 0; i < n; ++i) {
                for (int j = i + 1; j < n; ++j) {
                    for (int k = j + 1; k < n; ++k) {
                        vector<int> z{0, 1, 2}; 
                        do {
                            if (v[i][z[0]] > max(v[j][z[0]], v[k][z[0]])) {
                                if (v[j][z[1]] > max(v[i][z[1]], v[k][z[1]])) {
                                    if (v[k][z[2]] > max(v[i][z[2]], v[j][z[2]])) {
                                        // print(v[i]); 
                                        // print(v[j]); 
                                        // print(v[k]); 
                                        ans = max(ans, (v[i][z[0]] + v[j][z[1]] + v[k][z[2]])); 
                                        // cout << (v[i][z[0]] + v[j][z[1]] + v[k][z[2]]) << '\n'; 
                                    }
                                }
                            }
                        } while (next_permutation(z.begin(), z.end())); 
                    }
                }
            }

                    cout << ans << '\n'; 
        exit(0); 
        }


    }

    for (auto [x, y, z]: v) {
        f[x].push_back({y, z}); 
    }

    



    set<pair<int, int>> st, ts; 
    int sx = -1, sy = -1; 

    int ans = -1; 
    for (auto & [d1, v]: f) {
        for (auto [x, y]: v) {
            if (x < sx && y < sy) {
                ans = max(ans, d1 + sx + sy); 
                // cout << d1 << ' ' << sx << ' ' << sy << '\n'; 
            }
        }

        for (auto [x, y]: v) {
            if (x >= sx && y >= sy) {
                if (st.find({x, y}) != st.end()) continue; 
                
                auto it = st.upper_bound({x, y}); 

                if (it != st.begin()) {
                    it--; 
                    if ((*it).second > y) {
                        sx = x; 
                        sy = (*it).second; 
                    }
                } 

                auto ti = ts.upper_bound({y, x}); 

                if (ti != ts.begin()) {
                    ti--; 
                    if ((*ti).second > x) {
                        sy = y; 
                        sx = (*ti).second; 
                    }
                }

                st.insert({x, y});
                ts.insert({y, x}); 
            } else if (x > sx) {
                sx = x; 
            } else if (y > sy) {
                sy = y; 
            }
            while (st.size()) {
                auto [x, y] = *st.begin(); 
                if (x <= sx && y <= sy) {
                    st.erase(st.begin()); 
                } else {
                    break; 
                }
            }
            while (ts.size()) {
                auto [y, x] = *ts.begin(); 
                if (x <= sx && y <= sy) {
                    ts.erase(ts.begin()); 
                } else {
                    break; 
                }
            }
        }


    }

    cout << ans << "\n"; 


    return 0;
}

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