#pragma GCC optimize("unroll-loops")
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()
#define print(a) \
for (auto &x : a) \
cout << x << " "; \
cout << endl;
#define printmp(a) \
for (auto &x : a) \
cout << x.fs << " " << x.ss << endl;
const int mod = 998244353;
void solve(){
int n;
cin >> n;
vector<array<int, 3>> a(n);
for(int i = 0; i < n; i ++)
cin >> a[i][0] >> a[i][1] >> a[i][2];
set<int, greater<int>> a1, a2, a3;
for(int i = 0; i < n; i ++)
a1.insert(a[i][0]), a2.insert(a[i][1]), a3.insert(a[i][2]);
map<int, int> mp1, mp2, mp3;
for(auto x : a1)
mp1[x] = mp1.size();
for(auto x : a2)
mp2[x] = mp2.size();
for(auto x : a3)
mp3[x] = mp3.size();
vector<int> cnt1(n + 1), cnt2(n + 1), cnt3(n + 1);
for(int i = 0; i < n; i ++)
cnt1[mp1[a[i][0]]] ++, cnt2[mp2[a[i][1]]] ++, cnt3[mp3[a[i][2]]] ++;
vector<bool> removed(n);
set<array<int, 2>, greater<array<int, 2>>> s1, s2, s3;
for(int i = 0; i < n; i ++){
s1.insert({a[i][0] + a[i][1], i});
s2.insert({a[i][0] + a[i][2], i});
s3.insert({a[i][1] + a[i][2], i});
}
for(int i = 0; i < n; i ++){
array<int, 2> x = *s1.begin(), y = *s2.begin(), z = *s3.begin();
s1.erase(s1.begin());
s2.erase(s2.begin());
s3.erase(s3.begin());
if((a1.empty() ? -1000 : *a1.begin()) + (a2.empty() ? -1000 : *a2.begin()) == x[0] && !removed[x[1]]){
removed[x[1]] = true;
cnt1[mp1[a[x[1]][0]]] --;
cnt2[mp2[a[x[1]][1]]] --;
cnt3[mp3[a[x[1]][2]]] --;
s2.erase({a[x[1]][0] + a[x[1]][2], x[1]});
s3.erase({a[x[1]][1] + a[x[1]][2], x[1]});
if(cnt1[mp1[a[x[1]][0]]] == 0)
a1.erase(a1.begin());
if(cnt2[mp2[a[x[1]][1]]] == 0)
a2.erase(a2.begin());
if(cnt3[mp3[a[x[1]][2]]] == 0)
a3.erase(a3.find(a[x[1]][2]));
}
else if((a1.empty() ? -1000 : *a1.begin()) + (a3.empty() ? -1000 : *a3.begin()) == y[0] && !removed[y[1]]){
removed[y[1]] = true;
cnt1[mp1[a[y[1]][0]]] --;
cnt2[mp2[a[y[1]][1]]] --;
cnt3[mp3[a[y[1]][2]]] --;
s1.erase({a[y[1]][0] + a[y[1]][1], y[1]});
s3.erase({a[y[1]][1] + a[y[1]][2], y[1]});
if(cnt1[mp1[a[y[1]][0]]] == 0)
a1.erase(a1.begin());
if(cnt2[mp2[a[y[1]][1]]] == 0)
a2.erase(a2.find(a[y[1]][1]));
if(cnt3[mp3[a[y[1]][2]]] == 0)
a3.erase(a3.begin());
}
else if((a2.empty() ? -1000 : *a2.begin()) + (a3.empty() ? -1000 : *a3.begin()) == z[0] && !removed[z[1]]){
removed[z[1]] = true;
cnt1[mp1[a[z[1]][0]]] --;
cnt2[mp2[a[z[1]][1]]] --;
cnt3[mp3[a[z[1]][2]]] --;
s1.erase({a[z[1]][0] + a[z[1]][1], z[1]});
s2.erase({a[z[1]][0] + a[z[1]][2], z[1]});
if(cnt1[mp1[a[z[1]][0]]] == 0)
a1.erase(a1.find(a[z[1]][0]));
if(cnt2[mp2[a[z[1]][1]]] == 0)
a2.erase(a2.begin());
if(cnt3[mp3[a[z[1]][2]]] == 0)
a3.erase(a3.begin());
}
else{
break;
}
}
if(a1.empty())
cout << -1;
else
cout << *a1.begin() + *a2.begin() + *a3.begin();
}
signed main()
{
fastio int t = 1;
// cin >> t;
while (t--)
{
solve();
// cout << endl;
}
}
Compilation message
team.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
2 | #pragma gcc optimize("Ofast")
|
team.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
3 | #pragma GCC optimization("Ofast")
|
team.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
4 | #pragma optimize(Ofast)
|
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
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 |
1 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
600 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
