#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using lld = long double;
const int inf = 1e9;
// #ifndef ONLINE_JUDGE
// #include "E:\Personal\cpp_codes\debugalgo.h"
// #else
// #define debug(x)
// #endif
int get(vector<array<int,3>>&b, int idx)
{
int n = b.size();
vector<array<int,3>> a = b;
sort(a.begin(),a.end(), [&](array<int,3>x, array<int,3>y){
return x[idx]<y[idx];
});
// debug(a);
// int mxx = a.back()[idx];
priority_queue<pair<int,int>> pqy,pqz;
vector<array<int,3>> curr;
int l = 0;
int mxy = -inf, mxz = -inf;
int ans = -1;
for(int i=0; i<n; i++)
{
// debug("___________________________");
// debug(i,mxy,mxz,ans);
// debug(pqy,pqz);
if(a[i][idx]==a[l][idx])
{
curr.push_back({i,a[i][(idx+1)%3],a[i][(idx+2)%3]});
}
else
{
while(!curr.empty())
{
pqy.push({curr.back()[1],curr.back()[0]});
pqz.push({curr.back()[2],curr.back()[0]});
curr.pop_back();
}
curr.push_back({i,a[i][(idx+1)%3],a[i][(idx+2)%3]});
l = i;
}
// debug(i,pqy,pqz);
if(!pqy.empty() && pqy.top().second!=pqz.top().second && a[pqy.top().second][(idx+3)%3]!=pqz.top().second && a[pqz.top().second][(idx+2)%3]!=pqy.top().second)
{
mxy = pqy.top().first;
mxz = pqz.top().first;
}
// debug(idx,i,mxy,mxz);
if(a[i][(idx+1)%3]<mxy && a[i][(idx+2)%3]<mxz)
{
ans = max(ans, a[i][idx]+mxy+mxz);
}
// debug(i,mxy,mxz,ans);
// debug(pqy,pqz);
}
// debug(idx,ans);
return ans;
}
void solve()
{
int n;
cin >> n;
vector<array<int,3>> a(n);
int mxx = 0, mxy = 0, mxz = 0;
int mnx = inf, mny = inf, mnz = inf;
for (int i = 0; i < n; i++)
{
cin >> a[i][0]>>a[i][1]>>a[i][2];
mxx = max(mxx,a[i][0]);
mxy = max(mxy,a[i][1]);
mxz = max(mxz,a[i][2]);
mnx = min(mnx, a[i][0]);
mny = min(mny, a[i][1]);
mnz = min(mnz, a[i][2]);
}
vector<array<int,3>> b;
for(int i=0; i<n; i++)
{
int cnt = 0;
if(a[i][0]==mxx) cnt++;
if(a[i][1]==mxy) cnt++;
if(a[i][2]==mxz) cnt++;
if(cnt>=2) continue;
b.push_back(a[i]);
}
swap(a,b);
n = a.size();
if(n<=2)
{
cout<<"-1\n";
return;
}
int ans = -1;
for(int i=0; i<3; i++)
{
ans = max(ans, get(a,i));
}
cout<<ans<<"\n";
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
// #ifndef ONLINE_JUDGE
// freopen("error.txt", "w", stderr);
// #endif
int tt = 1;
// cin >> tt;
while (tt--)
{
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 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 |
66 ms |
9372 KB |
Output is correct |
| 12 |
Incorrect |
41 ms |
7500 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 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 |
66 ms |
9372 KB |
Output is correct |
| 12 |
Incorrect |
41 ms |
7500 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 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 |
66 ms |
9372 KB |
Output is correct |
| 12 |
Incorrect |
41 ms |
7500 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
452 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
0 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 |
66 ms |
9372 KB |
Output is correct |
| 12 |
Incorrect |
41 ms |
7500 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 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 |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
344 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
0 ms |
344 KB |
Output is correct |
| 12 |
Correct |
0 ms |
344 KB |
Output is correct |
| 13 |
Correct |
0 ms |
348 KB |
Output is correct |
| 14 |
Correct |
0 ms |
348 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
