제출 #618660

#제출 시각아이디문제언어결과실행 시간메모리
618660CSQ31Team Contest (JOI22_team)C++17
37 / 100
2078 ms4352 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef pair<int,int> pii;
typedef long long int ll;
const int MAXN = 5e5;
array<ll,3>pts[MAXN];
int bmx[MAXN];
//i have rectangle queries but i cant do it offline?
//i can but its double log on 2s
//ok try n^2 first
int main()
{
	owo
	int n;
	cin>>n;
	vector<array<ll,3>>a(n);
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>a[i][j];
		}
	}
	sort(all(a),[&](array<ll,3>i,array<ll,3>j){return j[0] > i[0];});
	//cout<<"sorted"<<'\n';
	//for(int i=0;i<n;i++)cout<<a[i][0]<<" "<<a[i][1]<<" "<<a[i][2]<<'\n';
	ll ans = -1;
	for(int i=0;i<n;){
		int k = i;
		while(k+1<n && a[k][0] == a[k+1][0])k++;
		for(int x=i;x<=k;x++){
			for(int j=0;j<x;j++){
				if(a[x][0] == a[j][0])break;
				if(pts[j][2] <0)continue;
				if(pts[j][1] > a[x][1] && pts[j][2] >a[x][2]){
					ans = max(ans,a[x][0] + pts[j][0]);
				}
			}
		}
		for(int x=i;x<=k;x++){
			pts[x][0] = -2e9;
			pts[x][1] = a[x][1];
			for(int j=0;j<x;j++){
				if(a[j][1] > a[x][1] && a[j][2] < a[x][2]){
					pts[j][2] = max(pts[j][2],a[x][2]);
					pts[j][0] = pts[j][1] + pts[j][2];
				}
				if(a[j][1] < a[x][1] && a[j][2] > a[x][2]){
					pts[x][2] = max(pts[x][2],a[j][2]);
					pts[x][0] = pts[x][1] + pts[x][2];
				}
				
			}
		}
		i = k+1;
	}
	cout<<ans;
	
	
	
}
#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...