oj.uz

Submission #748507

# Submission time Handle Problem Language Result Execution time Memory
748507 2023-05-26T11:49:21 Z GrindMachine Team Contest (JOI22_team) C++17
73 / 100
 555 ms 785008 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 4e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

ll sp[N][N], ps[N][N], pp[N][N];

void solve(int test_case)
{
    ll n; cin >> n;
    vector<array<ll,3>> a(n);
    rep(i,n) rep(j,3) cin >> a[i][j];

    sort(all(a));
    a.resize(unique(all(a))-a.begin());
    n = sz(a);

    vector<ll> bx, by;
    rep(i,n){
        bx.pb(a[i][0]);
        by.pb(a[i][1]);
    }

    sort(all(bx));
    sort(all(by));
    bx.resize(unique(all(bx))-bx.begin());
    by.resize(unique(all(by))-by.begin());

    vector<ll> cx(n), cy(n);
    rep(i,n){
        cx[i] = lower_bound(all(bx),a[i][0]) - bx.begin() + 1;
        cy[i] = lower_bound(all(by),a[i][1]) - by.begin() + 1;
    }

    memset(sp,0x3f,sizeof sp);
    memset(ps,0x3f,sizeof ps);
    memset(pp,0,sizeof pp);

    rep(i,n){
        ll x = cx[i], y = cy[i];
        ll z = a[i][2];

        amin(sp[x][y], z);
        amin(ps[x][y], z);
        amax(pp[x][y], z);
    }

    rev(i,N-2,1){
        rep1(j,N-2){
            amin(sp[i][j], sp[i+1][j]);
            amin(sp[i][j], sp[i][j-1]);
        }
    }

    rep1(i,N-2){
        rev(j,N-2,1){
            amin(ps[i][j], ps[i-1][j]);
            amin(ps[i][j], ps[i][j+1]);
        }
    }

    rep1(i,N-2){
        rep1(j,N-2){
            amax(pp[i][j], pp[i-1][j]);
            amax(pp[i][j], pp[i][j-1]);
        }
    }

    ll ans = -1;

    rep1(dx,N-2){
        rep1(dy,N-2){
            ll z1 = sp[dx][dy-1];
            ll z2 = ps[dx-1][dy];
            ll z3 = pp[dx-1][dy-1];

            if(z3 > z1 and z3 > z2){
                ll val = bx[dx-1] + by[dy-1] + z3;
                amax(ans, val);
            }
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 376984 KB Output is correct
2 Correct 322 ms 376972 KB Output is correct
3 Correct 347 ms 376896 KB Output is correct
4 Correct 344 ms 377024 KB Output is correct
5 Correct 372 ms 376908 KB Output is correct
6 Correct 324 ms 376972 KB Output is correct
7 Correct 315 ms 376972 KB Output is correct
8 Correct 321 ms 376972 KB Output is correct
9 Correct 347 ms 376972 KB Output is correct
10 Correct 336 ms 376972 KB Output is correct
11 Correct 312 ms 376988 KB Output is correct
12 Correct 318 ms 376896 KB Output is correct
13 Correct 317 ms 377096 KB Output is correct
14 Correct 316 ms 377000 KB Output is correct
15 Correct 323 ms 376992 KB Output is correct
16 Correct 329 ms 377000 KB Output is correct
17 Correct 343 ms 376996 KB Output is correct
18 Correct 310 ms 377004 KB Output is correct
19 Correct 349 ms 376996 KB Output is correct
20 Correct 315 ms 377084 KB Output is correct
21 Correct 313 ms 376992 KB Output is correct
22 Correct 311 ms 377080 KB Output is correct
23 Correct 314 ms 376980 KB Output is correct
24 Correct 326 ms 376992 KB Output is correct
25 Correct 325 ms 377076 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 376984 KB Output is correct
2 Correct 322 ms 376972 KB Output is correct
3 Correct 347 ms 376896 KB Output is correct
4 Correct 344 ms 377024 KB Output is correct
5 Correct 372 ms 376908 KB Output is correct
6 Correct 324 ms 376972 KB Output is correct
7 Correct 315 ms 376972 KB Output is correct
8 Correct 321 ms 376972 KB Output is correct
9 Correct 347 ms 376972 KB Output is correct
10 Correct 336 ms 376972 KB Output is correct
11 Correct 312 ms 376988 KB Output is correct
12 Correct 318 ms 376896 KB Output is correct
13 Correct 317 ms 377096 KB Output is correct
14 Correct 316 ms 377000 KB Output is correct
15 Correct 323 ms 376992 KB Output is correct
16 Correct 329 ms 377000 KB Output is correct
17 Correct 343 ms 376996 KB Output is correct
18 Correct 310 ms 377004 KB Output is correct
19 Correct 349 ms 376996 KB Output is correct
20 Correct 315 ms 377084 KB Output is correct
21 Correct 313 ms 376992 KB Output is correct
22 Correct 311 ms 377080 KB Output is correct
23 Correct 314 ms 376980 KB Output is correct
24 Correct 326 ms 376992 KB Output is correct
25 Correct 325 ms 377076 KB Output is correct
26 Correct 327 ms 377228 KB Output is correct
27 Correct 318 ms 377216 KB Output is correct
28 Correct 317 ms 377220 KB Output is correct
29 Correct 314 ms 377164 KB Output is correct
30 Correct 309 ms 377072 KB Output is correct
31 Correct 318 ms 377216 KB Output is correct
32 Correct 316 ms 377180 KB Output is correct
33 Correct 320 ms 377292 KB Output is correct
34 Correct 338 ms 377260 KB Output is correct
35 Correct 317 ms 377036 KB Output is correct
36 Correct 324 ms 377040 KB Output is correct
37 Correct 325 ms 377224 KB Output is correct
38 Correct 320 ms 377156 KB Output is correct
39 Correct 330 ms 377212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 376968 KB Output is correct
2 Correct 323 ms 376972 KB Output is correct
3 Correct 316 ms 376972 KB Output is correct
4 Correct 322 ms 376988 KB Output is correct
5 Correct 315 ms 376972 KB Output is correct
6 Correct 315 ms 377044 KB Output is correct
7 Correct 322 ms 376972 KB Output is correct
8 Correct 316 ms 376944 KB Output is correct
9 Correct 313 ms 376900 KB Output is correct
10 Correct 313 ms 376880 KB Output is correct
11 Correct 352 ms 380456 KB Output is correct
12 Correct 330 ms 379264 KB Output is correct
13 Correct 340 ms 379812 KB Output is correct
14 Correct 354 ms 380460 KB Output is correct
15 Correct 349 ms 380440 KB Output is correct
16 Correct 349 ms 380436 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 376968 KB Output is correct
2 Correct 323 ms 376972 KB Output is correct
3 Correct 316 ms 376972 KB Output is correct
4 Correct 322 ms 376988 KB Output is correct
5 Correct 315 ms 376972 KB Output is correct
6 Correct 315 ms 377044 KB Output is correct
7 Correct 322 ms 376972 KB Output is correct
8 Correct 316 ms 376944 KB Output is correct
9 Correct 313 ms 376900 KB Output is correct
10 Correct 313 ms 376880 KB Output is correct
11 Correct 352 ms 380456 KB Output is correct
12 Correct 330 ms 379264 KB Output is correct
13 Correct 340 ms 379812 KB Output is correct
14 Correct 354 ms 380460 KB Output is correct
15 Correct 349 ms 380440 KB Output is correct
16 Correct 349 ms 380436 KB Output is correct
17 Correct 313 ms 376968 KB Output is correct
18 Correct 320 ms 376972 KB Output is correct
19 Correct 313 ms 377064 KB Output is correct
20 Correct 318 ms 376908 KB Output is correct
21 Correct 311 ms 377072 KB Output is correct
22 Correct 360 ms 380700 KB Output is correct
23 Correct 347 ms 380456 KB Output is correct
24 Correct 342 ms 379568 KB Output is correct
25 Correct 350 ms 380492 KB Output is correct
26 Correct 358 ms 380424 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 376968 KB Output is correct
2 Correct 323 ms 376972 KB Output is correct
3 Correct 316 ms 376972 KB Output is correct
4 Correct 322 ms 376988 KB Output is correct
5 Correct 315 ms 376972 KB Output is correct
6 Correct 315 ms 377044 KB Output is correct
7 Correct 322 ms 376972 KB Output is correct
8 Correct 316 ms 376944 KB Output is correct
9 Correct 313 ms 376900 KB Output is correct
10 Correct 313 ms 376880 KB Output is correct
11 Correct 352 ms 380456 KB Output is correct
12 Correct 330 ms 379264 KB Output is correct
13 Correct 340 ms 379812 KB Output is correct
14 Correct 354 ms 380460 KB Output is correct
15 Correct 349 ms 380440 KB Output is correct
16 Correct 349 ms 380436 KB Output is correct
17 Correct 313 ms 376968 KB Output is correct
18 Correct 320 ms 376972 KB Output is correct
19 Correct 313 ms 377064 KB Output is correct
20 Correct 318 ms 376908 KB Output is correct
21 Correct 311 ms 377072 KB Output is correct
22 Correct 360 ms 380700 KB Output is correct
23 Correct 347 ms 380456 KB Output is correct
24 Correct 342 ms 379568 KB Output is correct
25 Correct 350 ms 380492 KB Output is correct
26 Correct 358 ms 380424 KB Output is correct
27 Correct 331 ms 377028 KB Output is correct
28 Correct 313 ms 376908 KB Output is correct
29 Correct 318 ms 377080 KB Output is correct
30 Correct 311 ms 376908 KB Output is correct
31 Correct 312 ms 377212 KB Output is correct
32 Correct 311 ms 376948 KB Output is correct
33 Correct 308 ms 377032 KB Output is correct
34 Correct 373 ms 385076 KB Output is correct
35 Correct 373 ms 385720 KB Output is correct
36 Correct 381 ms 386816 KB Output is correct
37 Correct 368 ms 385368 KB Output is correct
38 Correct 355 ms 382120 KB Output is correct
39 Correct 339 ms 383092 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 376968 KB Output is correct
2 Correct 323 ms 376972 KB Output is correct
3 Correct 316 ms 376972 KB Output is correct
4 Correct 322 ms 376988 KB Output is correct
5 Correct 315 ms 376972 KB Output is correct
6 Correct 315 ms 377044 KB Output is correct
7 Correct 322 ms 376972 KB Output is correct
8 Correct 316 ms 376944 KB Output is correct
9 Correct 313 ms 376900 KB Output is correct
10 Correct 313 ms 376880 KB Output is correct
11 Correct 352 ms 380456 KB Output is correct
12 Correct 330 ms 379264 KB Output is correct
13 Correct 340 ms 379812 KB Output is correct
14 Correct 354 ms 380460 KB Output is correct
15 Correct 349 ms 380440 KB Output is correct
16 Correct 349 ms 380436 KB Output is correct
17 Correct 313 ms 376968 KB Output is correct
18 Correct 320 ms 376972 KB Output is correct
19 Correct 313 ms 377064 KB Output is correct
20 Correct 318 ms 376908 KB Output is correct
21 Correct 311 ms 377072 KB Output is correct
22 Correct 360 ms 380700 KB Output is correct
23 Correct 347 ms 380456 KB Output is correct
24 Correct 342 ms 379568 KB Output is correct
25 Correct 350 ms 380492 KB Output is correct
26 Correct 358 ms 380424 KB Output is correct
27 Correct 331 ms 377028 KB Output is correct
28 Correct 313 ms 376908 KB Output is correct
29 Correct 318 ms 377080 KB Output is correct
30 Correct 311 ms 376908 KB Output is correct
31 Correct 312 ms 377212 KB Output is correct
32 Correct 311 ms 376948 KB Output is correct
33 Correct 308 ms 377032 KB Output is correct
34 Correct 373 ms 385076 KB Output is correct
35 Correct 373 ms 385720 KB Output is correct
36 Correct 381 ms 386816 KB Output is correct
37 Correct 368 ms 385368 KB Output is correct
38 Correct 355 ms 382120 KB Output is correct
39 Correct 339 ms 383092 KB Output is correct
40 Correct 339 ms 377292 KB Output is correct
41 Correct 314 ms 377224 KB Output is correct
42 Correct 322 ms 377352 KB Output is correct
43 Correct 313 ms 377272 KB Output is correct
44 Correct 414 ms 387596 KB Output is correct
45 Correct 396 ms 387512 KB Output is correct
46 Correct 403 ms 387504 KB Output is correct
47 Correct 391 ms 387504 KB Output is correct
48 Correct 371 ms 382892 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 321 ms 376984 KB Output is correct
2 Correct 322 ms 376972 KB Output is correct
3 Correct 347 ms 376896 KB Output is correct
4 Correct 344 ms 377024 KB Output is correct
5 Correct 372 ms 376908 KB Output is correct
6 Correct 324 ms 376972 KB Output is correct
7 Correct 315 ms 376972 KB Output is correct
8 Correct 321 ms 376972 KB Output is correct
9 Correct 347 ms 376972 KB Output is correct
10 Correct 336 ms 376972 KB Output is correct
11 Correct 312 ms 376988 KB Output is correct
12 Correct 318 ms 376896 KB Output is correct
13 Correct 317 ms 377096 KB Output is correct
14 Correct 316 ms 377000 KB Output is correct
15 Correct 323 ms 376992 KB Output is correct
16 Correct 329 ms 377000 KB Output is correct
17 Correct 343 ms 376996 KB Output is correct
18 Correct 310 ms 377004 KB Output is correct
19 Correct 349 ms 376996 KB Output is correct
20 Correct 315 ms 377084 KB Output is correct
21 Correct 313 ms 376992 KB Output is correct
22 Correct 311 ms 377080 KB Output is correct
23 Correct 314 ms 376980 KB Output is correct
24 Correct 326 ms 376992 KB Output is correct
25 Correct 325 ms 377076 KB Output is correct
26 Correct 327 ms 377228 KB Output is correct
27 Correct 318 ms 377216 KB Output is correct
28 Correct 317 ms 377220 KB Output is correct
29 Correct 314 ms 377164 KB Output is correct
30 Correct 309 ms 377072 KB Output is correct
31 Correct 318 ms 377216 KB Output is correct
32 Correct 316 ms 377180 KB Output is correct
33 Correct 320 ms 377292 KB Output is correct
34 Correct 338 ms 377260 KB Output is correct
35 Correct 317 ms 377036 KB Output is correct
36 Correct 324 ms 377040 KB Output is correct
37 Correct 325 ms 377224 KB Output is correct
38 Correct 320 ms 377156 KB Output is correct
39 Correct 330 ms 377212 KB Output is correct
40 Correct 315 ms 376968 KB Output is correct
41 Correct 323 ms 376972 KB Output is correct
42 Correct 316 ms 376972 KB Output is correct
43 Correct 322 ms 376988 KB Output is correct
44 Correct 315 ms 376972 KB Output is correct
45 Correct 315 ms 377044 KB Output is correct
46 Correct 322 ms 376972 KB Output is correct
47 Correct 316 ms 376944 KB Output is correct
48 Correct 313 ms 376900 KB Output is correct
49 Correct 313 ms 376880 KB Output is correct
50 Correct 352 ms 380456 KB Output is correct
51 Correct 330 ms 379264 KB Output is correct
52 Correct 340 ms 379812 KB Output is correct
53 Correct 354 ms 380460 KB Output is correct
54 Correct 349 ms 380440 KB Output is correct
55 Correct 349 ms 380436 KB Output is correct
56 Correct 313 ms 376968 KB Output is correct
57 Correct 320 ms 376972 KB Output is correct
58 Correct 313 ms 377064 KB Output is correct
59 Correct 318 ms 376908 KB Output is correct
60 Correct 311 ms 377072 KB Output is correct
61 Correct 360 ms 380700 KB Output is correct
62 Correct 347 ms 380456 KB Output is correct
63 Correct 342 ms 379568 KB Output is correct
64 Correct 350 ms 380492 KB Output is correct
65 Correct 358 ms 380424 KB Output is correct
66 Correct 331 ms 377028 KB Output is correct
67 Correct 313 ms 376908 KB Output is correct
68 Correct 318 ms 377080 KB Output is correct
69 Correct 311 ms 376908 KB Output is correct
70 Correct 312 ms 377212 KB Output is correct
71 Correct 311 ms 376948 KB Output is correct
72 Correct 308 ms 377032 KB Output is correct
73 Correct 373 ms 385076 KB Output is correct
74 Correct 373 ms 385720 KB Output is correct
75 Correct 381 ms 386816 KB Output is correct
76 Correct 368 ms 385368 KB Output is correct
77 Correct 355 ms 382120 KB Output is correct
78 Correct 339 ms 383092 KB Output is correct
79 Correct 339 ms 377292 KB Output is correct
80 Correct 314 ms 377224 KB Output is correct
81 Correct 322 ms 377352 KB Output is correct
82 Correct 313 ms 377272 KB Output is correct
83 Correct 414 ms 387596 KB Output is correct
84 Correct 396 ms 387512 KB Output is correct
85 Correct 403 ms 387504 KB Output is correct
86 Correct 391 ms 387504 KB Output is correct
87 Correct 371 ms 382892 KB Output is correct
88 Runtime error 555 ms 785008 KB Execution killed with signal 11
89 Halted 0 ms 0 KB -