oj.uz

Submission #1058791

# Submission time Handle Problem Language Result Execution time Memory
1058791 2024-08-14T13:52:06 Z Boas Team Contest (JOI22_team) C++17
0 / 100
 19 ms 2228 KB 
#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)(2e9 + 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)), mnZonY(sz(ys) + 1, vi(sz(xs) + 1));
    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]);
            mnZonX[x][y] = 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], z2 = mnZonY[y][x];
            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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 2140 KB Output is correct
15 Incorrect 1 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 2140 KB Output is correct
15 Incorrect 1 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 19 ms 2228 KB Output is correct
12 Incorrect 12 ms 1640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 19 ms 2228 KB Output is correct
12 Incorrect 12 ms 1640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 19 ms 2228 KB Output is correct
12 Incorrect 12 ms 1640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 19 ms 2228 KB Output is correct
12 Incorrect 12 ms 1640 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 600 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 2140 KB Output is correct
15 Incorrect 1 ms 600 KB Output isn't correct
16 Halted 0 ms 0 KB -