Submission #892208

#TimeUsernameProblemLanguageResultExecution timeMemory
892208vjudge1Team Contest (JOI22_team)C++17
8 / 100
289 ms43340 KiB
#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"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...