Submission #795076

#	Time	Username	Problem	Language	Result	Execution time	Memory
795076		vjudge1	Team Contest (JOI22_team)	C++17	64 / 100	2069 ms	9660 KiB

team

// Author : حسن

#include <bits/stdc++.h>



using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 2e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N][4] = {},  us[N] , dp[N] = {} , b[309][309][4];

ll get(int i, int j, int k){
    ll mn = 0;
    while(i > 0){
        int x = j;
        while(x > 0){
        mn = max(mn , b[i][x][k]);
        x -= x & (-x);
        }
        i -= (i & (-i));
    }
    return mn;
}
void add(int i , int j , ll y , int k){
    while(i <= 300){
        int x = j;
        while(x <= 300){
        b[i][x][k] = max(b[i][x][k] , y);
        x += (x & -x);
        }
        i += i & (-i);
    }
}

void solve(){
    ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
    cin>>n;
    vector<pair<int,pair<int,int>>>v;
    for(i =1; i <= n; i++){
        cin>>a[i][1]>>a[i][2]>>a[i][3] ;
            mx = max({mx , a[i][1] , a[i][2] , a[i][3]});
            v.pb({a[i][1] ,{ a[i][2] , a[i][3]}});
    }
    if(mx <= 300){
        mx = -1;
    for(i = 1; i <= n; i++){
        add(a[i][2] , a[i][3], a[i][1] , 1);
        add(a[i][1] , a[i][3], a[i][2] , 2);
        add(a[i][1] , a[i][2], a[i][3] , 3);
    }
    for(i = 1; i <= 300; i++){
        for(j = 1; j <= 300; j++){
            for(x = 1; x <= 300; x++){
                if(get(j - 1, x - 1 , 1) >= i && get(i - 1 , x - 1 , 2) >= j && get(i - 1 , j - 1 , 3) >= x)
                    mx = max(mx , i + j + x);
            }
        }
    }
    cout<<mx<<"\n";
    }else {
        mx = -1;
        sort(all(v));
        for(i = 0; i < n; i++)
            a[i+  1][1] = v[i].fi , a[i + 1][2] = v[i].se.fi , a[i + 1][3] = v[i].se.se;
        for(i = 1;i  <= n; i++){
            l = i;
            x = 0;
            set<int>st;
            for(j = i + 1; j <= n; j++){
                while(a[j][1] > a[l][1]){
                    if(a[l][2] < a[i][2] && a[l][3] > a[i][3])
                    x = max(x , a[l][3]) , st.insert(a[l][3]);
                    l++;
                }
                if(st.size() && a[i][2] > a[j][2]){
                    auto it = st.end();
                    it--;
                    if(*it > a[j][3]){
                    mx = max(mx , a[i][2] + a[j][1] + *it);
                    }
                }
            }
        }
        for(i = 1;i  <= n; i++){
            l = i;
            x = 0;
            set<int>st;
            for(j = i + 1; j <= n; j++){
                while(a[j][1] > a[l][1]){
                    if(a[l][3] < a[i][3] && a[l][2] > a[i][2])
                    x = max(x , a[l][2]) , st.insert(a[l][2]);
                    l++;
                }
                if(st.size() && a[i][3] > a[j][3]){
                    auto it = st.end();
                    it--;
                    if(*it > a[j][2]){
                    mx = max(mx , a[i][3] + a[j][1] + *it);
                    }
                }
            }
        }
        cout<<mx<<"\n";
    }
}

int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

team.cpp: In function 'void solve()':
team.cpp:54:8: warning: unused variable 'q' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |        ^
team.cpp:54:20: warning: unused variable 'm' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                    ^
team.cpp:54:26: warning: unused variable 'z' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                          ^
team.cpp:54:30: warning: unused variable 's' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                              ^
team.cpp:54:38: warning: unused variable 'f' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                      ^
team.cpp:54:45: warning: unused variable 'r' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                             ^
team.cpp:54:49: warning: unused variable 'k' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                 ^
team.cpp:54:57: warning: unused variable 'y' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                         ^
team.cpp:54:61: warning: unused variable 'mn' [-Wunused-variable]
   54 |     ll q , i , j , m ,n, z , s  = 0, f, l , r , k , x , y , mn  = 1e18 , mx = -1;
      |                                                             ^~

• Subtask 1: 8 / 8
• Subtask 2: 29 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27