AtCoder WA了一个测试点求条
查看原帖
AtCoder WA了一个测试点求条
627293
FanMingxuan楼主2024/7/26 08:50

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e18;
const int N = 1000005;
int a[N],b[N],c[N],pos[N];
priority_queue<pair<int,int> > qAB,qAC,qBA,qBC,qCA,qCB;

int Ckmax(int a,int b,int c,int d,int e,int f){
	return max(a,max(b,max(c,max(d,max(e,f)))));
}

signed main(){
	int ans = 0;
	int x,y,z;
	cin>>x>>y>>z;
	for(int i = 1;i <= x;++ i){
		cin>>a[i]>>b[i]>>c[i];
		qAB.push({b[i] - a[i],i});
		qAC.push({c[i] - a[i],i});
		ans += a[i];
		pos[i] = 1;
	}
	for(int i = x + 1;i <= x + y;++ i){
		cin>>a[i]>>b[i]>>c[i];
		qBA.push({a[i] - b[i],i});
		qBC.push({c[i] - b[i],i});
		ans += b[i];
		pos[i] = 2;
	}
	for(int i = x + y + 1;i <= x + y + z;++ i){
		cin>>a[i]>>b[i]>>c[i];
		qCA.push({a[i] - c[i],i});
		qCB.push({b[i] - c[i],i});
		ans += c[i];
		pos[i] = 3;
	}
	while(true){
		int wAB = -INF,wAC = -INF,wBA = -INF,wBC = -INF,wCA = -INF,wCB = -INF;
		int pAB = -114514,pAC = -114514,pBA = -114514,pBC = -114514,pCA = -114514,pCB = -114514;
		while(!qAB.empty() && pos[qAB.top().second] != 1) qAB.pop();
		if(!qAB.empty()) wAB = qAB.top().first,pAB = qAB.top().second;
		while(!qAC.empty() && pos[qAC.top().second] != 1) qAC.pop();
		if(!qAC.empty()) wAC = qAC.top().first,pAC = qAC.top().second;
		while(!qBA.empty() && pos[qBA.top().second] != 2) qBA.pop();
		if(!qBA.empty()) wBA = qBA.top().first,pBA = qBA.top().second;
		while(!qBC.empty() && pos[qBC.top().second] != 2) qBC.pop();
		if(!qBC.empty()) wBC = qBC.top().first,pBC = qBC.top().second;
		while(!qCA.empty() && pos[qCA.top().second] != 3) qCA.pop();
		if(!qCA.empty()) wCA = qCA.top().first,pCA = qCA.top().second;
		while(!qCB.empty() && pos[qCB.top().second] != 3) qCB.pop();
		if(!qCB.empty()) wCB = qCB.top().first,pCB = qCB.top().second;
		int wmax = Ckmax(-INF,wAB + wBA,wAC + wCA,wBC + wCB,wAB + wBC + wCA,wAC + wCB + wBA);
		if(wmax <= 0) break;
		ans += wmax;
		if(wAB != -INF && wBA != -INF && wmax == wAB + wBA){
			qAB.pop();
			qBA.pop();
			pos[pAB] = 2;
			pos[pBA] = 1;
			qAB.push({b[pBA] - a[pBA],pBA});
			qAC.push({c[pBA] - a[pBA],pBA});
			qBA.push({a[pAB] - b[pAB],pAB});
			qBC.push({c[pAB] - b[pAB],pAB});
		}
		else if(wAC != -INF && wCA != -INF && wmax == wAC + wCA){
			qAC.pop();
			qCA.pop();
			pos[pAC] = 3;
			pos[pCA] = 1;
			qAC.push({c[pCA] - a[pCA],pCA});
			qAB.push({b[pCA] - a[pCA],pCA});
			qCA.push({a[pAC] - c[pAC],pAC});
			qCB.push({b[pAC] - c[pAC],pAC});
		}
		else if(wBC != -INF && wCB != -INF && wmax == wBC + wCB){
			qBC.pop();
			qCB.pop();
			pos[pBC] = 3;
			pos[pCB] = 2;
			qBC.push({c[pCB] - b[pCB],pBA});
			qBA.push({a[pCB] - b[pCB],pBA});
			qCB.push({b[pBC] - c[pBC],pAB});
			qCA.push({a[pBC] - c[pBC],pAB});
		}
		else if(wAB != -INF && wBC != -INF && wCA != -INF && wmax == wAB + wBC + wCA){
			qAB.pop();
			qBC.pop();
			qCA.pop();
			pos[pAB] = 2;
			pos[pBC] = 3;
			pos[pCA] = 1;
			qAB.push({b[pCA] - a[pCA],pCA});
			qAC.push({c[pCA] - a[pCA],pCA});
			qBC.push({c[pAB] - b[pAB],pAB});
			qBA.push({a[pAB] - b[pAB],pAB});
			qCA.push({a[pBC] - c[pBC],pBC});
			qCB.push({b[pBC] - c[pBC],pBC});
		}
		else if(wAC != -INF && wCB != -INF && wBA != -INF && wmax == wAC + wCB + wBA){
			qAC.pop();
			qCB.pop();
			qBA.pop();
			pos[pAC] = 3;
			pos[pCB] = 2;
			pos[pBA] = 1;
			qAC.push({c[pBA] - a[pBA],pBA});
			qAB.push({b[pBA] - a[pBA],pBA});
			qCB.push({b[pAC] - c[pAC],pAC});
			qCA.push({a[pAC] - c[pAC],pAC});
			qBA.push({a[pCB] - b[pCB],pCB});
			qBC.push({c[pCB] - b[pCB],pCB});
		}
	}
	cout<<ans;
	return 0;
}

提交记录

2024/7/26 08:50
加载中...