oj.uz

Submission #549934

# Submission time Handle Problem Language Result Execution time Memory
549934 2022-04-16T21:17:44 Z BalintR Team Contest (JOI22_team) C++17
0 / 100
 71 ms 39488 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);

    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 18 ms 39428 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 18 ms 39380 KB Output is correct
6 Correct 18 ms 39488 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 18 ms 39424 KB Output is correct
9 Correct 18 ms 39404 KB Output is correct
10 Correct 18 ms 39488 KB Output is correct
11 Correct 18 ms 39420 KB Output is correct
12 Correct 22 ms 39476 KB Output is correct
13 Correct 20 ms 39380 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 18 ms 39428 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 18 ms 39380 KB Output is correct
6 Correct 18 ms 39488 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 18 ms 39424 KB Output is correct
9 Correct 18 ms 39404 KB Output is correct
10 Correct 18 ms 39488 KB Output is correct
11 Correct 18 ms 39420 KB Output is correct
12 Correct 22 ms 39476 KB Output is correct
13 Correct 20 ms 39380 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 1 ms 452 KB Output is correct
3 Correct 18 ms 39488 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 20 ms 39404 KB Output is correct
6 Correct 18 ms 39380 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39396 KB Output is correct
9 Correct 18 ms 39468 KB Output is correct
10 Correct 18 ms 39404 KB Output is correct
11 Runtime error 71 ms 9212 KB Execution killed with signal 11
12 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 1 ms 452 KB Output is correct
3 Correct 18 ms 39488 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 20 ms 39404 KB Output is correct
6 Correct 18 ms 39380 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39396 KB Output is correct
9 Correct 18 ms 39468 KB Output is correct
10 Correct 18 ms 39404 KB Output is correct
11 Runtime error 71 ms 9212 KB Execution killed with signal 11
12 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 1 ms 452 KB Output is correct
3 Correct 18 ms 39488 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 20 ms 39404 KB Output is correct
6 Correct 18 ms 39380 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39396 KB Output is correct
9 Correct 18 ms 39468 KB Output is correct
10 Correct 18 ms 39404 KB Output is correct
11 Runtime error 71 ms 9212 KB Execution killed with signal 11
12 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 1 ms 452 KB Output is correct
3 Correct 18 ms 39488 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 20 ms 39404 KB Output is correct
6 Correct 18 ms 39380 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 23 ms 39396 KB Output is correct
9 Correct 18 ms 39468 KB Output is correct
10 Correct 18 ms 39404 KB Output is correct
11 Runtime error 71 ms 9212 KB Execution killed with signal 11
12 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 18 ms 39428 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 18 ms 39380 KB Output is correct
6 Correct 18 ms 39488 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 18 ms 39424 KB Output is correct
9 Correct 18 ms 39404 KB Output is correct
10 Correct 18 ms 39488 KB Output is correct
11 Correct 18 ms 39420 KB Output is correct
12 Correct 22 ms 39476 KB Output is correct
13 Correct 20 ms 39380 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 -