제출 #1058806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058806		Boas	Team Contest (JOI22_team)	C++17	73 / 100	590 ms	1048576 KiB

team

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T1, typename T2>
using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using indexed_set = indexed_map<T, null_type>;

#define loop(x, i) for (int i = 0; i < (x); i++)
#define loop1(x, i) for (int i = 1; i <= (x); i++)
#define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--)
#define itloop(x) for (auto it = begin(x); x != end(x); it++)
#define itrev(x) for (auto it = rbegin(x); x != rend(x); it++)
// #define int long long
#define INF ((int32_t)(4e8 + 1))
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define existsIn(x, l) (count(ALL(l), x) > 0)
#define removeIn(x, l) l.erase(find(ALL(l), x))
#define pb push_back
#define sz(x) (int)(x).size()
#define F first
#define S second
#define var const auto &
#define foreach(l) for (var e : l)

typedef int8_t in8;
typedef int16_t in16;
typedef int32_t in32;
typedef int64_t in64;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vii> vvii;
typedef vector<viii> vviii;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;
typedef vector<si> vsi;
typedef vector<sii> vsii;
typedef vector<vsi> vvsi;
typedef vector<string> vstr;
typedef vector<vector<string>> vvstr;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vi::iterator viit;
typedef si::iterator siit;

void solve()
{
    int n;
    cin >> n;
    viii beavers(n);
    map<int, int> xCom;
    map<int, int> yCom;
    si xs, ys;
    for (auto &[x, y, z] : beavers)
    {
        cin >> x >> y >> z;
        xs.insert(x);
        ys.insert(y);
    }
    vi xComRev(sz(xs) + 1), yComRev(sz(ys) + 1);
    auto it = xs.begin();
    for (int i = 1; i <= sz(xs); i++)
    {
        xCom[*it] = i;
        xComRev[i] = *it;
        it++;
    }
    it = ys.begin();
    for (int i = 1; i <= sz(ys); i++)
    {
        yCom[*it] = i;
        yComRev[i] = *it;
        it++;
    }
    for (auto &[x, y, z] : beavers)
    {
        x = xCom[x];
        y = yCom[y];
    }
    vvi z(sz(xs) + 1, vi(sz(ys) + 1, -INF));
    vvi maxZ = z;
    vvi minZ(sz(xs) + 1, vi(sz(ys) + 1, INF));
    vvi mnZonX(sz(xs) + 1, vi(sz(ys) + 1, INF)), mnZonY(sz(ys) + 1, vi(sz(xs) + 1, INF));
    for (var[x, y, Z] : beavers)
    {
        z[x][y] = max(z[x][y], Z);
        minZ[x][y] = min(minZ[x][y], Z);
    }
    for (int x = 1; x <= sz(xs); x++)
    {
        int zMn = INF;
        for (int y = 1; y <= sz(ys); y++)
        {
            zMn = min(zMn, minZ[x][y]);
            mnZonX[x][y] = zMn;
        }
    }
    for (int y = 1; y <= sz(ys); y++)
    {
        int zMn = INF;
        for (int x = 1; x <= sz(xs); x++)
        {
            zMn = min(zMn, minZ[x][y]);
            mnZonY[y][x] = zMn;
        }
    }
    int res = -1;
    for (int x = 1; x <= sz(xs); x++)
    {
        for (int y = 1; y <= sz(ys); y++)
        {
            maxZ[x][y] = max({maxZ[x - 1][y], maxZ[x][y - 1], z[x][y]});

            int z3 = maxZ[x - 1][y - 1];
            int z1 = mnZonX[x][y - 1], z2 = mnZonY[y][x - 1];
            if (z1 == -INF || z2 == -INF)
                continue;
            if (z3 > max(z1, z2))
                res = max(res, xComRev[x] + yComRev[y] + z3);
        }
    }

    cout << res << endl;
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• 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: 0 / 27