oj.uz

Submission #770344

# Submission time Handle Problem Language Result Execution time Memory
770344 2023-07-01T05:50:33 Z ttamx Team Contest (JOI22_team) C++14
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=150005;
const int M=4005;

int n,nx,ny,nz;
int x[N],y[N],z[N];
vector<ll> px,py,pz;
pair<int,int> vx[N],vy[N];
int mn[M][M],dp[M][M];
ll ans=-1;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> x[i] >> y[i] >> z[i];
        px.emplace_back(x[i]);
        py.emplace_back(y[i]);
        pz.emplace_back(z[i]);
    }
    px.emplace_back(-1e18);
    py.emplace_back(-1e18);
    pz.emplace_back(-1e18);
    sort(px.begin(),px.end());
    sort(py.begin(),py.end());
    sort(pz.begin(),pz.end());
    px.erase(unique(px.begin(),px.end()),px.end());
    py.erase(unique(py.begin(),py.end()),py.end());
    pz.erase(unique(pz.begin(),pz.end()),pz.end());
    nx=px.size();
    ny=py.size();
    nz=pz.size();
    z[0]=n+1;
    for(int i=1;i<=nx;i++)for(int j=1;j<=ny;j++)mn[i][j]=nz+1;
    for(int i=1;i<=n;i++){
        x[i]=lower_bound(px.begin(),px.end(),x[i])-px.begin();
        y[i]=lower_bound(py.begin(),py.end(),y[i])-py.begin();
        z[i]=lower_bound(pz.begin(),pz.end(),z[i])-pz.begin();
        dp[x[i]][y[i]]=max(dp[x[i]][y[i]],z[i]);
        if(z[i]<z[vx[x[i]].second])vx[x[i]].second=i;
        if(z[vx[x[i]].second]<z[vx[x[i]].first])swap(vx[x[i]].first,vx[x[i]].second);
        if(z[i]<z[vy[y[i]].second])vy[y[i]].second=i;
        if(z[vy[y[i]].second]<z[vy[y[i]].first])swap(vy[y[i]].first,vy[y[i]].second);
    }
    for(int i=1;i<=nx;i++){
        for(int j=1;j<=ny;j++){
            dp[i][j]=max({dp[i][j],dp[i-1][j],dp[i][j-1]});
            if(vx[i].first!=vy[i].second){
                int res=max(z[vx[i].first],z[vy[i].first]);
                if(dp[i-1][j-1]>res)ans=max(ans,px[i]+py[j]+pz[dp[i-1][j-1]]);
            }else{
                int res=max(z[vx[i].first],z[vy[i].second]);
                if(dp[i-1][j-1]>res)ans=max(ans,px[i]+py[j]+pz[dp[i-1][j-1]]);
                res=max(z[vx[i].second],z[vy[i].first]);
                if(dp[i-1][j-1]>res)ans=max(ans,px[i]+py[j]+pz[dp[i-1][j-1]]);
            }
        }
    }
    cout << ans;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -