| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 795314 | vjudge1 | Team Contest (JOI22_team) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std ;
const int N = 15e4, NS = 4e4 ;
bool flag1, flag2, flag3 ;
int n, ans = -1, x[N + 1], y[N + 1], z[N + 1] ;
set<pair<int, pair<int, int>>> s ;
vector<pair<int, pair<int, int>>> v ;
int mx[2 * n + 1][2 * n + 1] = {}, num[2 * n + 1][2 * n + 1] = {}, kol = 0 ;
int func(int i, int j, int q)
{
if(x[i] > x[j] && x[i] > x[q] && y[j] > y[i] && y[j] > y[q] && z[i] < z[q] && z[j] < z[q])
return x[i] + y[j] + z[q] ;
else
return -1 ;
}
int func1(int i, int j, int q)
{
if(v[i].fi > v[j].fi && v[i].fi > v[q].fi && v[j].se.fi > v[i].se.fi && v[j].se.fi > v[q].se.fi && v[i].se.se < v[q].se.se && v[j].se.se < v[q].se.se)
return v[i].fi + v[j].se.fi + v[q].se.se ;
else
return -1 ;
}
signed main()
{
ios_base::sync_with_stdio( 0 ) ;
cin.tie( 0 ) ;
cout.tie( 0 ) ;
cin >> n ;
for(int i = 1 ; i <= n ; i++)
{
cin >> x[i] >> y[i] >> z[i] ;
if(x[i] > 5 || y[i] > 5 || z[i] > 5)flag1 = 1 ;
if(x[i] > 20 || y[i] > 20 || z[i] > 20)flag2 = 1 ;
if(x[i] > 4000 || y[i] > 4000 || z[i] > 4000)flag3 = 1 ;
s.insert({x[i], {y[i], z[i]}}) ;
}
if(n <= 4000)
{
set<int> s1 ;
map<int, int> mp, ob ;
for(int i = 1 ; i <= n ; i++)
{
s1.insert(x[i]) ;
s1.insert(y[i]) ;
}
for(int i : s1)
kol++, mp[i] = kol ;
for(int i = 1 ; i <= n ; i++)
{
ob[mp[x[i]]] = x[i] ;
ob[mp[y[i]]] = y[i] ;
x[i] = mp[x[i]] ;
y[i] = mp[y[i]] ;
num[x[i]][y[i]] = z[i] ;
}
for(int i = 1 ; i <= 2 * n ; i++)
{
int now = 0 ;
for(int j = 1 ; j <= 2 * n ; j++)
{
now = max(now, num[i][j]) ;
mx[i][j] = max(now, mx[i - 1][j]) ;
}
}
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
{
if(x[i] <= x[j] || y[j] <= y[i] || mx[x[i] - 1][y[j] - 1] <= max(z[i], z[j]))
continue ;
ans = max(ans, ob[x[i]] + ob[y[j]] + mx[x[i] - 1][y[j] - 1]) ;
}
cout << ans << '\n' ;
return 0 ;
}
if(!flag3)
{
}
if(!flag2)
{
for(auto i : s)
v.push_back(i) ;
for(int i = 1 ; i <= 20 ; i++)
for(int j = 1 ; j <= 20 ; j++)
for(int q = 1 ; q <= 20 ; q++)
{
bool fl1 = 0, fl2 = 0, fl3 = 0 ;
for(auto now : v)
{
if(now.fi == i && now.se.fi < j && now.se.se < q)fl1 = 1 ;
if(now.fi < i && now.se.fi == j && now.se.se < q)fl2 = 1 ;
if(now.fi < i && now.se.fi < j && now.se.se == q)fl3 = 1 ;
}
if(fl1 && fl2 && fl3)
ans = max(ans, i + j + q) ;
}
cout << ans ;
return 0 ;
}
if(n <= 300)
{
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
{
if(i == j)
continue ;
for(int q = 1 ; q <= n ; q++)
{
if(j == q || i == q)
continue ;
ans = max(ans, func(i, j, q)) ;
}
}
cout << ans << '\n' ;
return 0 ;
}
return 0 ;
}