oj.uz

Submission #549935

# Submission time Handle Problem Language Result Execution time Memory
549935 2022-04-16T21:19:47 Z BalintR Team Contest (JOI22_team) C++17
0 / 100
 49 ms 39508 KB 
#include <bits/stdc++.h>
using namespace std;

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef complex<double> cmplx;
template <typename T> using minPq = priority_queue<T, vector<T>, greater<T>>;
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define ms(a, x) memset(a, x, sizeof(a))
#define pb push_back
#define fs first
#define sn second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int) (v).size())
#define lbv(v, x) (lower_bound((v).begin(), (v).end(), x) - (v).begin())
#define ubv(v, x) (upper_bound((v).begin(), (v).end(), x) - (v).begin())
template <typename T> inline void UNIQUE(vector<T> &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);
#define FR(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORR(i, a, b) for(int i = (a); i >= (b); i--)
#define dbg(x) {cout << #x << ' ' << x << endl;}
#define dbgArr(arr, n) {cout << #arr; FR(_i, n) cout << ' ' << arr[_i]; cout << endl;}

typedef array<int, 3> trip;

const int MN = 4005;
int n;
vector<trip> vec;
vi ys, zs;
int mxZPref[MN], mxYPref[MN], mnZ[MN], mxZ[MN];

int main(){
    boost();
    cin >> n;
    FR(i, n){
        int a, b, c;
        cin >> a >> b >> c;
        vec.pb({a, b, c});
        ys.pb(b);
        zs.pb(c);
    }

    UNIQUE(vec);
    UNIQUE(ys);
    UNIQUE(zs);
    n = SZ(ys);

    int ans = -1;
    ms(mnZ, INF);
    int lst = 0, prvX = vec[0][0];

    FR(i, SZ(vec)){
        if(vec[i][0] != prvX){
            FOR(j, lst, i){
                auto [x, y, z] = vec[j];
                int yPos = lbv(ys, y);
                int zPos = lbv(zs, z);

                int mz = 0;
                FR(k, yPos) mz = max(mz, mxZPref[k]);
                if(mz > z) mxZ[yPos] = max(mxZ[yPos], mz);
                mxYPref[zPos] = max(mxYPref[zPos], y);
                mnZ[yPos] = min(mnZ[yPos], z);

                int mxY = 0;
                FR(k, zPos) mxY = max(mxY, mxYPref[k]);
                if(mxY){
                    int yp1 = lbv(ys, mxY);
                    mxZ[yp1] = max(mxZ[yp1], z);
                }
                mxZPref[yPos] = max(mxZPref[yPos], z);
            }
            prvX = vec[i][0];
            lst = i;
        }

        auto [x, y, z] = vec[i];
        int yPos = lbv(ys, y);
        int mxSum = 0;

        FOR(j, yPos+1, n) mxSum = max(mxSum, (ys[j] + mxZ[j]) * (mxZ[j] > z));
        if(mxSum) ans = max(ans, mxSum + x);
    }

    if(ans == -1) vi vec(1e7, 1234);

    cout << ans << '\n';
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 17 ms 39488 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 39388 KB Output is correct
6 Correct 19 ms 39452 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 21 ms 39376 KB Output is correct
9 Correct 20 ms 39492 KB Output is correct
10 Correct 19 ms 39456 KB Output is correct
11 Correct 22 ms 39380 KB Output is correct
12 Correct 18 ms 39508 KB Output is correct
13 Correct 19 ms 39440 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 17 ms 39488 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 39388 KB Output is correct
6 Correct 19 ms 39452 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 21 ms 39376 KB Output is correct
9 Correct 20 ms 39492 KB Output is correct
10 Correct 19 ms 39456 KB Output is correct
11 Correct 22 ms 39380 KB Output is correct
12 Correct 18 ms 39508 KB Output is correct
13 Correct 19 ms 39440 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 39364 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 22 ms 39468 KB Output is correct
6 Correct 26 ms 39420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39484 KB Output is correct
9 Correct 21 ms 39372 KB Output is correct
10 Correct 19 ms 39364 KB Output is correct
11 Correct 49 ms 4660 KB Output is correct
12 Incorrect 30 ms 2668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 39364 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 22 ms 39468 KB Output is correct
6 Correct 26 ms 39420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39484 KB Output is correct
9 Correct 21 ms 39372 KB Output is correct
10 Correct 19 ms 39364 KB Output is correct
11 Correct 49 ms 4660 KB Output is correct
12 Incorrect 30 ms 2668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 39364 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 22 ms 39468 KB Output is correct
6 Correct 26 ms 39420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39484 KB Output is correct
9 Correct 21 ms 39372 KB Output is correct
10 Correct 19 ms 39364 KB Output is correct
11 Correct 49 ms 4660 KB Output is correct
12 Incorrect 30 ms 2668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 19 ms 39364 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 22 ms 39468 KB Output is correct
6 Correct 26 ms 39420 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39484 KB Output is correct
9 Correct 21 ms 39372 KB Output is correct
10 Correct 19 ms 39364 KB Output is correct
11 Correct 49 ms 4660 KB Output is correct
12 Incorrect 30 ms 2668 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 17 ms 39488 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 19 ms 39388 KB Output is correct
6 Correct 19 ms 39452 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 21 ms 39376 KB Output is correct
9 Correct 20 ms 39492 KB Output is correct
10 Correct 19 ms 39456 KB Output is correct
11 Correct 22 ms 39380 KB Output is correct
12 Correct 18 ms 39508 KB Output is correct
13 Correct 19 ms 39440 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Halted 0 ms 0 KB -