Submission #795170

#	Time	Username	Problem	Language	Result	Execution time	Memory
795170		vjudge1	Team Contest (JOI22_team)	C++17	37 / 100	2068 ms	376700 KiB

team

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

struct My{
    int x, y, z;

    bool operator < (My &b) {
        return x == b.x ? (y == b.y ? z < b.z : y < b.y) : x < b.x;
    }
};

map < int , map < int, int > > mp;


int get(int x, int y) {
    auto it = mp.lower_bound(x);
    if(it == mp.begin()) {
        return 0;
    }
    -- it;
    auto it2 = it->second.lower_bound(y);
    if(it2 == it->second.begin()) {
        return 0;
    }
    -- it2;
    return it2->second;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k;
    cin >> n;
    vector < My > V(n);
    for(auto &[x, y, z] : V) {
        cin >> x >> y >> z;
    }
    sort(V.begin(), V.end());
    for(int i = 0; i < n; ++ i) {
        auto it = mp.find(V[i].x);
        if(it == mp.end()) {
            mp[V[i].x];
            it = mp.find(V[i].x);
        }
        auto it2 = it->second.find(V[i].y);
        if(it2 == it->second.end()) {
            it->second[V[i].y] = V[i].z;
        } else {
            it2->second = max(it2->second, V[i].z);
        }
        if(i + 1 < n && V[i].x == V[i + 1].x) {
            continue;
        }
        if(it != mp.begin()) {
            auto pre_mp = prev(it);
            for(auto &[key, val] : pre_mp->second) {
                auto it2 = it->second.find(key);
                if(it2 == it->second.end()) {
                    it->second[key] = val;
                } else {
                    it2->second = max(it2->second, val);
                }
            }
        } 
        int mx = 0;
        for(auto &[key, val] : it->second) {
            mx = max(mx, val);
            val = mx;
        }
    }
    /**
    for(auto &[x, y, z] : V) {
        cout << x << ' ' << y << ' ' << z << '\n';
    }
    cout << '\n';
    for(auto &[key, val] : mp) {
        for(auto &[key2, val2] : val) {
            cout << key << ' ' << key2 << ' ' << val2 << '\n';
        }
    }
    // */
    int ans = 0;
    for(int i = n; i --> 0;) {
        for(int j = i; j --> 0;) {
            if(V[i].x > V[j].x && V[j].y > V[i].y) {
                k = get(V[i].x, V[j].y);
                if(k > V[i].z && k > V[j].z) {
                    ans = max(ans, V[i].x + V[j].y + k);
                }
            }
        }
    }
    cout << (ans ? ans : -1);
} 

Compilation message (stderr)

team.cpp:36:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   36 | main() {
      | ^~~~
team.cpp: In function 'int main()':
team.cpp:44:12: warning: unused variable 'm' [-Wunused-variable]
   44 |     int n, m, k;
      |            ^

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