제출 #795273

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
795273		vjudge1	Team Contest (JOI22_team)	C++17	55 / 100	2039 ms	376664 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;
}

int mtx[4040][4040];

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, mx = 0;
    cin >> n;
    vector < My > V(n);
    for(auto &[x, y, z] : V) {
        cin >> x >> y >> z;
        mx = max({mx, x, y, z});
    }
    if(mx <= 4000) {
        for(auto &[x, y, z] : V) {
            mtx[x][y] = max(mtx[x][y], z);
            auto it = mp.find(x);
            if(it == mp.end()) {
                mp[x];
                it = mp.find(x);
            }
            auto it2 = it->second.find(y);
            if(it2 == it->second.end()) {
                it->second[y] = z;
            } else {
                it2->second = min(it2->second, z);
            }
        }
        for(int i = 1; i <= mx; ++ i) {
            for(int j = 1; j <= mx; ++j) {
                mtx[i][j] = max({mtx[i][j], mtx[i][j - 1], mtx[i - 1][j]});
            }
        }
        mx = 0;
        for(auto it = prev(mp.end());  it != mp.begin(); it --) {
            int x = it->first;
            for(auto &[y, z] : it->second) {
                for(auto it2 = prev(it);; it2 --) {
                    int x2 = it2->first;
                    if(x2 >= x) {
                        continue;
                    }
                    for(auto &[y2, z2] : it2->second) {
                        if(y2 <= y) {
                            continue;
                        }
                        k = mtx[x - 1][y2 - 1];
                        if(k > z && k > z2) {
                            mx = max(mx, x + y2 + k);
                        }
                    }
                    if(it2 == mp.begin()) {
                        break;
                    }
                }
            }
        }
        cout << (mx ? mx : -1);
        return 0;
    }
    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);
                }
            }
        } 
        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';
        }
    }
    // */
    mx = 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) {
                    mx = max(mx, V[i].x + V[j].y + k);
                }
            }
        }
    }
    cout << (mx ? mx : -1);
} 

컴파일 시 표준 에러 (stderr) 메시지

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

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