#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 time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
392 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
289 ms |
524 KB |
Output is correct |
15 |
Correct |
111 ms |
348 KB |
Output is correct |
16 |
Correct |
175 ms |
504 KB |
Output is correct |
17 |
Correct |
210 ms |
348 KB |
Output is correct |
18 |
Correct |
224 ms |
348 KB |
Output is correct |
19 |
Correct |
260 ms |
344 KB |
Output is correct |
20 |
Correct |
244 ms |
596 KB |
Output is correct |
21 |
Correct |
89 ms |
348 KB |
Output is correct |
22 |
Correct |
114 ms |
348 KB |
Output is correct |
23 |
Correct |
34 ms |
348 KB |
Output is correct |
24 |
Correct |
119 ms |
348 KB |
Output is correct |
25 |
Correct |
129 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
392 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
289 ms |
524 KB |
Output is correct |
15 |
Correct |
111 ms |
348 KB |
Output is correct |
16 |
Correct |
175 ms |
504 KB |
Output is correct |
17 |
Correct |
210 ms |
348 KB |
Output is correct |
18 |
Correct |
224 ms |
348 KB |
Output is correct |
19 |
Correct |
260 ms |
344 KB |
Output is correct |
20 |
Correct |
244 ms |
596 KB |
Output is correct |
21 |
Correct |
89 ms |
348 KB |
Output is correct |
22 |
Correct |
114 ms |
348 KB |
Output is correct |
23 |
Correct |
34 ms |
348 KB |
Output is correct |
24 |
Correct |
119 ms |
348 KB |
Output is correct |
25 |
Correct |
129 ms |
596 KB |
Output is correct |
26 |
Runtime error |
4 ms |
1112 KB |
Execution killed with signal 11 |
27 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
79 ms |
20768 KB |
Output is correct |
12 |
Correct |
51 ms |
14336 KB |
Output is correct |
13 |
Correct |
61 ms |
17372 KB |
Output is correct |
14 |
Correct |
78 ms |
22564 KB |
Output is correct |
15 |
Runtime error |
87 ms |
43340 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
79 ms |
20768 KB |
Output is correct |
12 |
Correct |
51 ms |
14336 KB |
Output is correct |
13 |
Correct |
61 ms |
17372 KB |
Output is correct |
14 |
Correct |
78 ms |
22564 KB |
Output is correct |
15 |
Runtime error |
87 ms |
43340 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
79 ms |
20768 KB |
Output is correct |
12 |
Correct |
51 ms |
14336 KB |
Output is correct |
13 |
Correct |
61 ms |
17372 KB |
Output is correct |
14 |
Correct |
78 ms |
22564 KB |
Output is correct |
15 |
Runtime error |
87 ms |
43340 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
79 ms |
20768 KB |
Output is correct |
12 |
Correct |
51 ms |
14336 KB |
Output is correct |
13 |
Correct |
61 ms |
17372 KB |
Output is correct |
14 |
Correct |
78 ms |
22564 KB |
Output is correct |
15 |
Runtime error |
87 ms |
43340 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
1 ms |
392 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
289 ms |
524 KB |
Output is correct |
15 |
Correct |
111 ms |
348 KB |
Output is correct |
16 |
Correct |
175 ms |
504 KB |
Output is correct |
17 |
Correct |
210 ms |
348 KB |
Output is correct |
18 |
Correct |
224 ms |
348 KB |
Output is correct |
19 |
Correct |
260 ms |
344 KB |
Output is correct |
20 |
Correct |
244 ms |
596 KB |
Output is correct |
21 |
Correct |
89 ms |
348 KB |
Output is correct |
22 |
Correct |
114 ms |
348 KB |
Output is correct |
23 |
Correct |
34 ms |
348 KB |
Output is correct |
24 |
Correct |
119 ms |
348 KB |
Output is correct |
25 |
Correct |
129 ms |
596 KB |
Output is correct |
26 |
Runtime error |
4 ms |
1112 KB |
Execution killed with signal 11 |
27 |
Halted |
0 ms |
0 KB |
- |