Submission #795305

#	Time	Username	Problem	Language	Result	Execution time	Memory
795305		vjudge1	Team Contest (JOI22_team)	C++14	18 / 100	150 ms	125956 KiB

team

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std ;
const int N = 15e4 ;
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 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> s ;
        int mx[n + 1][n + 1] = {}, num[n + 1][n + 1] = {}, kol = 0 ;
        map<int, int> mp, ob ;
        for(int i = 1 ; i <= n ; i++)
        {
            s.insert(x[i]) ;
            s.insert(y[i]) ;
        }
        for(int i : s)
            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 <= n ; i++)
        {
            int now = 0 ;
            for(int j = 1 ; j <= 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++)
//                cout << num[i][j] << ' ' ;
//            cout << '\n' ;
//        }
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= n ; j++)
            {
                if(i == j || 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 ;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27