답안 #748499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748499	2023-05-26T11:26:55 Z	GrindMachine	Team Contest (JOI22_team)	C++17	37 / 100	2000 ms	134224 KB

team

// 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;

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];

    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;
    }

    ll dp[N][N];
    memset(dp,0,sizeof dp);

    rep(i,n){
        amax(dp[cx[i]][cy[i]], a[i][2]);
    }

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

    ll ans = -1;

    rep(i,n){
        rep(j,n){
            if(i == j) conts;

            auto [x1,y1,z1] = a[i];
            auto [x2,y2,z2] = a[j];

            if(x1 > x2 and y2 > y1){
                ll mxz = dp[cx[i]-1][cy[j]-1];
                if(mxz > z1 and mxz > z2){
                    ll val = x1 + y2 + mxz;
                    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

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	125772 KB	Output is correct
2	Correct	112 ms	125764 KB	Output is correct
3	Correct	113 ms	125796 KB	Output is correct
4	Correct	111 ms	125772 KB	Output is correct
5	Correct	120 ms	125852 KB	Output is correct
6	Correct	112 ms	125852 KB	Output is correct
7	Correct	112 ms	125844 KB	Output is correct
8	Correct	112 ms	125832 KB	Output is correct
9	Correct	115 ms	125864 KB	Output is correct
10	Correct	115 ms	125772 KB	Output is correct
11	Correct	115 ms	125844 KB	Output is correct
12	Correct	112 ms	125852 KB	Output is correct
13	Correct	110 ms	125772 KB	Output is correct
14	Correct	116 ms	126008 KB	Output is correct
15	Correct	114 ms	125884 KB	Output is correct
16	Correct	113 ms	125796 KB	Output is correct
17	Correct	114 ms	125864 KB	Output is correct
18	Correct	115 ms	125876 KB	Output is correct
19	Correct	113 ms	125884 KB	Output is correct
20	Correct	113 ms	125828 KB	Output is correct
21	Correct	113 ms	125860 KB	Output is correct
22	Correct	111 ms	125888 KB	Output is correct
23	Correct	116 ms	125960 KB	Output is correct
24	Correct	112 ms	125856 KB	Output is correct
25	Correct	113 ms	125880 KB	Output is correct

Subtask #2
29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	125772 KB	Output is correct
2	Correct	112 ms	125764 KB	Output is correct
3	Correct	113 ms	125796 KB	Output is correct
4	Correct	111 ms	125772 KB	Output is correct
5	Correct	120 ms	125852 KB	Output is correct
6	Correct	112 ms	125852 KB	Output is correct
7	Correct	112 ms	125844 KB	Output is correct
8	Correct	112 ms	125832 KB	Output is correct
9	Correct	115 ms	125864 KB	Output is correct
10	Correct	115 ms	125772 KB	Output is correct
11	Correct	115 ms	125844 KB	Output is correct
12	Correct	112 ms	125852 KB	Output is correct
13	Correct	110 ms	125772 KB	Output is correct
14	Correct	116 ms	126008 KB	Output is correct
15	Correct	114 ms	125884 KB	Output is correct
16	Correct	113 ms	125796 KB	Output is correct
17	Correct	114 ms	125864 KB	Output is correct
18	Correct	115 ms	125876 KB	Output is correct
19	Correct	113 ms	125884 KB	Output is correct
20	Correct	113 ms	125828 KB	Output is correct
21	Correct	113 ms	125860 KB	Output is correct
22	Correct	111 ms	125888 KB	Output is correct
23	Correct	116 ms	125960 KB	Output is correct
24	Correct	112 ms	125856 KB	Output is correct
25	Correct	113 ms	125880 KB	Output is correct
26	Correct	203 ms	126212 KB	Output is correct
27	Correct	205 ms	126184 KB	Output is correct
28	Correct	198 ms	126212 KB	Output is correct
29	Correct	180 ms	126192 KB	Output is correct
30	Correct	151 ms	126132 KB	Output is correct
31	Correct	193 ms	126140 KB	Output is correct
32	Correct	186 ms	126028 KB	Output is correct
33	Correct	210 ms	126200 KB	Output is correct
34	Correct	169 ms	126128 KB	Output is correct
35	Correct	117 ms	125924 KB	Output is correct
36	Correct	125 ms	125916 KB	Output is correct
37	Correct	133 ms	126044 KB	Output is correct
38	Correct	131 ms	126076 KB	Output is correct
39	Correct	132 ms	125964 KB	Output is correct

Subtask #3
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	125736 KB	Output is correct
2	Correct	118 ms	125896 KB	Output is correct
3	Correct	115 ms	125848 KB	Output is correct
4	Correct	115 ms	125772 KB	Output is correct
5	Correct	114 ms	125844 KB	Output is correct
6	Correct	112 ms	125848 KB	Output is correct
7	Correct	118 ms	125804 KB	Output is correct
8	Correct	116 ms	125900 KB	Output is correct
9	Correct	113 ms	125812 KB	Output is correct
10	Correct	121 ms	125852 KB	Output is correct
11	Execution timed out	2098 ms	134224 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	125736 KB	Output is correct
2	Correct	118 ms	125896 KB	Output is correct
3	Correct	115 ms	125848 KB	Output is correct
4	Correct	115 ms	125772 KB	Output is correct
5	Correct	114 ms	125844 KB	Output is correct
6	Correct	112 ms	125848 KB	Output is correct
7	Correct	118 ms	125804 KB	Output is correct
8	Correct	116 ms	125900 KB	Output is correct
9	Correct	113 ms	125812 KB	Output is correct
10	Correct	121 ms	125852 KB	Output is correct
11	Execution timed out	2098 ms	134224 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	125736 KB	Output is correct
2	Correct	118 ms	125896 KB	Output is correct
3	Correct	115 ms	125848 KB	Output is correct
4	Correct	115 ms	125772 KB	Output is correct
5	Correct	114 ms	125844 KB	Output is correct
6	Correct	112 ms	125848 KB	Output is correct
7	Correct	118 ms	125804 KB	Output is correct
8	Correct	116 ms	125900 KB	Output is correct
9	Correct	113 ms	125812 KB	Output is correct
10	Correct	121 ms	125852 KB	Output is correct
11	Execution timed out	2098 ms	134224 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	125736 KB	Output is correct
2	Correct	118 ms	125896 KB	Output is correct
3	Correct	115 ms	125848 KB	Output is correct
4	Correct	115 ms	125772 KB	Output is correct
5	Correct	114 ms	125844 KB	Output is correct
6	Correct	112 ms	125848 KB	Output is correct
7	Correct	118 ms	125804 KB	Output is correct
8	Correct	116 ms	125900 KB	Output is correct
9	Correct	113 ms	125812 KB	Output is correct
10	Correct	121 ms	125852 KB	Output is correct
11	Execution timed out	2098 ms	134224 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #7
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	113 ms	125772 KB	Output is correct
2	Correct	112 ms	125764 KB	Output is correct
3	Correct	113 ms	125796 KB	Output is correct
4	Correct	111 ms	125772 KB	Output is correct
5	Correct	120 ms	125852 KB	Output is correct
6	Correct	112 ms	125852 KB	Output is correct
7	Correct	112 ms	125844 KB	Output is correct
8	Correct	112 ms	125832 KB	Output is correct
9	Correct	115 ms	125864 KB	Output is correct
10	Correct	115 ms	125772 KB	Output is correct
11	Correct	115 ms	125844 KB	Output is correct
12	Correct	112 ms	125852 KB	Output is correct
13	Correct	110 ms	125772 KB	Output is correct
14	Correct	116 ms	126008 KB	Output is correct
15	Correct	114 ms	125884 KB	Output is correct
16	Correct	113 ms	125796 KB	Output is correct
17	Correct	114 ms	125864 KB	Output is correct
18	Correct	115 ms	125876 KB	Output is correct
19	Correct	113 ms	125884 KB	Output is correct
20	Correct	113 ms	125828 KB	Output is correct
21	Correct	113 ms	125860 KB	Output is correct
22	Correct	111 ms	125888 KB	Output is correct
23	Correct	116 ms	125960 KB	Output is correct
24	Correct	112 ms	125856 KB	Output is correct
25	Correct	113 ms	125880 KB	Output is correct
26	Correct	203 ms	126212 KB	Output is correct
27	Correct	205 ms	126184 KB	Output is correct
28	Correct	198 ms	126212 KB	Output is correct
29	Correct	180 ms	126192 KB	Output is correct
30	Correct	151 ms	126132 KB	Output is correct
31	Correct	193 ms	126140 KB	Output is correct
32	Correct	186 ms	126028 KB	Output is correct
33	Correct	210 ms	126200 KB	Output is correct
34	Correct	169 ms	126128 KB	Output is correct
35	Correct	117 ms	125924 KB	Output is correct
36	Correct	125 ms	125916 KB	Output is correct
37	Correct	133 ms	126044 KB	Output is correct
38	Correct	131 ms	126076 KB	Output is correct
39	Correct	132 ms	125964 KB	Output is correct
40	Correct	112 ms	125736 KB	Output is correct
41	Correct	118 ms	125896 KB	Output is correct
42	Correct	115 ms	125848 KB	Output is correct
43	Correct	115 ms	125772 KB	Output is correct
44	Correct	114 ms	125844 KB	Output is correct
45	Correct	112 ms	125848 KB	Output is correct
46	Correct	118 ms	125804 KB	Output is correct
47	Correct	116 ms	125900 KB	Output is correct
48	Correct	113 ms	125812 KB	Output is correct
49	Correct	121 ms	125852 KB	Output is correct
50	Execution timed out	2098 ms	134224 KB	Time limit exceeded
51	Halted	0 ms	0 KB	-

답안 #748499

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 29.0 / 29.0

Subtask #3 0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
8.0 / 8.0

Subtask #2
29.0 / 29.0

Subtask #3
0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0