| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 770348 |
2023-07-01T05:52:02 Z |
ttamx |
Team Contest (JOI22_team) |
C++14 |
|
48 ms |
6960 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[j].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[j].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[j].first]);
if(dp[i-1][j-1]>res)ans=max(ans,px[i]+py[j]+pz[dp[i-1][j-1]]);
}
}
}
cout << ans;
}
| # |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3540 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3540 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
292 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
48 ms |
6960 KB |
Output is correct |
| 12 |
Incorrect |
24 ms |
4616 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
292 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
48 ms |
6960 KB |
Output is correct |
| 12 |
Incorrect |
24 ms |
4616 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
292 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
48 ms |
6960 KB |
Output is correct |
| 12 |
Incorrect |
24 ms |
4616 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 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 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
292 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
48 ms |
6960 KB |
Output is correct |
| 12 |
Incorrect |
24 ms |
4616 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
336 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
4 ms |
3540 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
1360 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
