Submission #892208

#	Time	Username	Problem	Language	Result	Execution time	Memory
892208		vjudge1	Team Contest (JOI22_team)	C++17	8 / 100	289 ms	43340 KiB

team

#include <bits/stdc++.h>
#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
vector< pair <int,int> > mp1[500],mp2[500],mp3[500];
vector <int> mn1[500],mn2[500],mn3[500];
signed main(){
    int n;
    cin>>n;
    vector <vector <int> > a;
    int mxx=0,mxy=0,mxz=0;
    for(int i=0;i<n;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a.pb({x,y,z});
        mxx=max(mxx,x);
        mxy=max(mxy,y);
        mxz=max(mxz,z);
        if(x<500 && y<500 && z<500){
            mp1[x].pb({y,z});
            mp2[y].pb({x,z});
            mp3[z].pb({x,y});
        }
        
    }
    if(n<=300){
        int res=-1;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                for(int k=j+1;k<n;k++){
                    bool flag=true;
                    int ans=0;
                    set <int> st;
                    for(int t=0;t<3;t++){
                        int mx=0,cnt=0,x=-1;
                        mx=max(a[i][t],mx);
                        mx=max(a[j][t],mx);
                        mx=max(a[k][t],mx);
                        if(mx==a[i][t]){
                            cnt++;x=i;
                        }
                        if(mx==a[j][t]){
                            cnt++;x=j;
                        }
                        if(mx==a[k][t]){
                            cnt++;x=k;
                        }
                        if(cnt==1){
                            ans+=mx;
                            st.insert(x);
                        }
                        else flag=false;
                    }
                    if(flag && st.size()==3)res=max(res,ans);
                }
            }
        }
        cout<<res<<"\n";return 0;
    }
    
    for(int i=1;i<=mxx;i++){
        sort(all(mp1[i]));
    }
    for(int i=1;i<=mxx;i++){
        int mn=1e9;
        for(auto y : mp1[i]){
            mn=min(mn,y.ss);
            mn1[i].pb(mn);
        }
    }
    
    for(int i=1;i<=mxy;i++){
        sort(all(mp2[i]));
    }
    for(int i=1;i<=mxy;i++){
        int mn=1e9;
        for(auto y : mp2[i]){
            mn=min(mn,y.ss);
            mn2[i].pb(mn);
        }
    }
    
    
    for(int i=1;i<=mxz;i++){
        sort(all(mp3[i]));
    }
    for(int i=1;i<=mxy;i++){
        int mn=1e9;
        for(auto y : mp3[i]){
            mn=min(mn,y.ss);
            mn3[i].pb(mn);
        }
    }
    
    int mx=-1;
    for(int i=1;i<=mxx;i++){
        for(int j=1;j<=mxy;j++){
            for(int k=1;k<=mxz;k++){
                
                bool ok1=0,ok2=0,ok3=0;
                if(mp1[i].size()==0 or mp2[j].size()==0 or mp3[k].size()==0)continue;
                
                
                pair <int,int> p={j-1,k};
                auto it=upper_bound(all(mp1[i]),p);
                if(it==mp1[i].end() && mn1[i].back()<k)ok1=1;
                else if(it!=mp1[i].begin() &&  mn1[i][it-mp1[i].begin()-1]<k)ok1=1;
                
                p={i-1,k};
                it=upper_bound(all(mp2[j]),p);
                if(it==mp2[j].end() && mn2[j].back()<k)ok2=1;
                else if(it!=mp2[j].begin() &&  mn2[j][it-mp2[j].begin()-1]<k)ok2=1;
                
                p={i-1,j};
                it=upper_bound(all(mp3[k]),p);
                if(it==mp3[k].end() && mn3[k].back()<j)ok3=1;
                else if(it!=mp3[k].begin() &&  mn3[k][it-mp3[k].begin()-1]<j)ok3=1;
                
                
                if(ok1 && ok2 && ok3){
                    mx=max(mx,i+j+k);
                }
            }
        }
    }
    cout<<mx<<"\n";
}

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