Submission #748497

# Submission time Handle Problem Language Result Execution time Memory
748497 2023-05-26T11:23:27 Z GrindMachine Team Contest (JOI22_team) C++17
0 / 100
2000 ms 254968 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;

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

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

    rep(i,n){
        auto [x,y,z] = a[i];
        amax(dp[x][y], z);
    }

    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[x1-1][y2-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;
}
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125776 KB Output is correct
2 Correct 116 ms 125860 KB Output is correct
3 Correct 116 ms 125848 KB Output is correct
4 Correct 113 ms 125856 KB Output is correct
5 Correct 118 ms 125772 KB Output is correct
6 Correct 113 ms 125740 KB Output is correct
7 Correct 118 ms 125856 KB Output is correct
8 Correct 112 ms 125848 KB Output is correct
9 Correct 116 ms 125860 KB Output is correct
10 Correct 114 ms 125852 KB Output is correct
11 Correct 117 ms 125784 KB Output is correct
12 Correct 118 ms 125856 KB Output is correct
13 Correct 112 ms 125744 KB Output is correct
14 Runtime error 160 ms 254968 KB Execution killed with signal 7
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125776 KB Output is correct
2 Correct 116 ms 125860 KB Output is correct
3 Correct 116 ms 125848 KB Output is correct
4 Correct 113 ms 125856 KB Output is correct
5 Correct 118 ms 125772 KB Output is correct
6 Correct 113 ms 125740 KB Output is correct
7 Correct 118 ms 125856 KB Output is correct
8 Correct 112 ms 125848 KB Output is correct
9 Correct 116 ms 125860 KB Output is correct
10 Correct 114 ms 125852 KB Output is correct
11 Correct 117 ms 125784 KB Output is correct
12 Correct 118 ms 125856 KB Output is correct
13 Correct 112 ms 125744 KB Output is correct
14 Runtime error 160 ms 254968 KB Execution killed with signal 7
15 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125848 KB Output is correct
2 Correct 114 ms 125992 KB Output is correct
3 Correct 112 ms 125772 KB Output is correct
4 Correct 112 ms 125828 KB Output is correct
5 Correct 113 ms 125852 KB Output is correct
6 Correct 118 ms 125852 KB Output is correct
7 Correct 118 ms 125772 KB Output is correct
8 Correct 123 ms 125856 KB Output is correct
9 Correct 123 ms 125860 KB Output is correct
10 Correct 120 ms 125900 KB Output is correct
11 Execution timed out 2078 ms 130216 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125848 KB Output is correct
2 Correct 114 ms 125992 KB Output is correct
3 Correct 112 ms 125772 KB Output is correct
4 Correct 112 ms 125828 KB Output is correct
5 Correct 113 ms 125852 KB Output is correct
6 Correct 118 ms 125852 KB Output is correct
7 Correct 118 ms 125772 KB Output is correct
8 Correct 123 ms 125856 KB Output is correct
9 Correct 123 ms 125860 KB Output is correct
10 Correct 120 ms 125900 KB Output is correct
11 Execution timed out 2078 ms 130216 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125848 KB Output is correct
2 Correct 114 ms 125992 KB Output is correct
3 Correct 112 ms 125772 KB Output is correct
4 Correct 112 ms 125828 KB Output is correct
5 Correct 113 ms 125852 KB Output is correct
6 Correct 118 ms 125852 KB Output is correct
7 Correct 118 ms 125772 KB Output is correct
8 Correct 123 ms 125856 KB Output is correct
9 Correct 123 ms 125860 KB Output is correct
10 Correct 120 ms 125900 KB Output is correct
11 Execution timed out 2078 ms 130216 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125848 KB Output is correct
2 Correct 114 ms 125992 KB Output is correct
3 Correct 112 ms 125772 KB Output is correct
4 Correct 112 ms 125828 KB Output is correct
5 Correct 113 ms 125852 KB Output is correct
6 Correct 118 ms 125852 KB Output is correct
7 Correct 118 ms 125772 KB Output is correct
8 Correct 123 ms 125856 KB Output is correct
9 Correct 123 ms 125860 KB Output is correct
10 Correct 120 ms 125900 KB Output is correct
11 Execution timed out 2078 ms 130216 KB Time limit exceeded
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 113 ms 125776 KB Output is correct
2 Correct 116 ms 125860 KB Output is correct
3 Correct 116 ms 125848 KB Output is correct
4 Correct 113 ms 125856 KB Output is correct
5 Correct 118 ms 125772 KB Output is correct
6 Correct 113 ms 125740 KB Output is correct
7 Correct 118 ms 125856 KB Output is correct
8 Correct 112 ms 125848 KB Output is correct
9 Correct 116 ms 125860 KB Output is correct
10 Correct 114 ms 125852 KB Output is correct
11 Correct 117 ms 125784 KB Output is correct
12 Correct 118 ms 125856 KB Output is correct
13 Correct 112 ms 125744 KB Output is correct
14 Runtime error 160 ms 254968 KB Execution killed with signal 7
15 Halted 0 ms 0 KB -