Submission #1268665

#TimeUsernameProblemLanguageResultExecution timeMemory
1268665k12_khoiTeam Contest (JOI22_team)C++17
37 / 100
2093 ms3268 KiB
#include <bits/stdc++.h>
using namespace std;

const int N=1.5e5+5;

struct skills
{
    int X,Y,Z;
} a[N];

bool cmp(skills x,skills y)
{
    return x.X<y.X;
}

int n,res;

namespace sub1
{
    void solve()
    {
        res=-1;
        for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if (j!=i)
        for (int k=1;k<=n;k++)
        if (k!=j)
        if (a[i].X>a[j].X and a[i].X>a[k].X and a[j].Y>a[i].Y and a[j].Y>a[k].Y and a[k].Z>a[i].Z and a[k].Z>a[j].Z)
            res=max(res,a[i].X+a[j].Y+a[k].Z);

        cout << res;
    }
}

namespace sub2
{
    int h,l,dp[N];
    vector <int> ve;

    void solve()
    {
        sort(a+1,a+n+1,cmp);

        ve.clear();
        for (int i=1;i<=n;i++)
        ve.push_back(a[i].Y);

        sort(ve.begin(),ve.end());
        ve.resize(unique(ve.begin(),ve.end())-ve.begin());
        h=ve.size();

        for (int i=1;i<=n;i++)
        a[i].Y=lower_bound(ve.begin(),ve.end(),a[i].Y)-ve.begin()+1;

        res=-1;
        l=1;
        for (int i=1;i<=n;i++)
        {
            while (a[l].X<a[i].X)
            {
                for (int j=1;j<l;j++)
                {
                    if (a[j].Y>a[l].Y and a[j].Z<a[l].Z)
                        dp[a[j].Y]=max(dp[a[j].Y],a[l].Z);

                    if (a[j].Y<a[l].Y and a[j].Z>a[l].Z)
                        dp[a[l].Y]=max(dp[a[l].Y],a[j].Z);
                }

                l++;
            }

            for (int j=a[i].Y+1;j<=h;j++)
            if (dp[j]>a[i].Z) res=max(res,a[i].X+ve[j-1]+dp[j]);
        }

        cout << res;
    }
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for (int i=1;i<=n;i++)
    cin >> a[i].X >> a[i].Y >> a[i].Z;

    sub2::solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...