比赛 2025.9.6 评测结果 AAWWWWWWWWWW
题目名称 Compatible Pairs 最终得分 17
用户昵称 zhyn 运行时间 1.699 s
代码语言 C++ 内存使用 13.96 MiB
提交时间 2025-09-06 11:24:39
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
#define ll long long
int n,a,b;
ll ans=0;
ll f=0;
struct node{
	int x,y;
};
node num[maxn];
map<int,int>m;
int dp[maxn][6];
void dfs(int s,ll sum){
	if(s==n+1){
		ans=max(ans,sum);
		return;
	}
	int u,v=num[s].x,p,minn;
	u=a-num[s].y;
	u=m[u];
	if(u!=0){
		if(u!=s){
			p=num[u].x;
			minn=min(num[s].x,num[u].x);
			num[s].x-=minn,num[u].x-=minn;
			dfs(s+1,sum+minn);
			num[s].x=v,num[u].x=p;
		}
		else{
			int q=num[s].x/2;
			num[s].x-=q;
			dfs(s+1,sum+q);
			num[s].x=v;
		}
		
	}
	if(a!=b){
		u=b-num[s].y;
		u=m[u];
		if(u!=0){
			if(u!=s){
				p=num[u].x;
				minn=min(num[s].x,num[u].x);
				num[s].x-=minn,num[u].x-=minn;
				dfs(s+1,sum+minn);
				num[s].x=v,num[u].x=p;
			}
			else{
				int q=num[s].x/2;
				num[s].x-=q;
				dfs(s+1,sum+q);
				num[s].x=v;
			}
		}
	}
	dfs(s+1,sum);
}

int main(){
	
	freopen("Compatible.in","r",stdin);
	freopen("Compatible.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>num[i].x>>num[i].y;
		m[num[i].y]=i;
	}
	if(n<=50){
		dfs(1,0);
		cout<<ans;
		return 0;
	}
	
	for(int i=1;i<=n;i++){
		int u=m[a-num[i].y];
		if(u!=0&&u>i){
			dp[i][1]+=min(num[i].x,num[u].x)+f;
		}
		else if(u==i){
			dp[i][1]+=num[i].x/2+f;
		}
		else{
			dp[i][1]=f;
		}
		int v=m[b-num[i].y];
		if(v!=0&&v>i){
			dp[i][2]+=min(num[i].x,num[v].x)+f;
		}
		else if(u==i){
			dp[i][2]+=num[i].x/2+f;
		}
		else{
			dp[i][2]=f;
		}
		if(u!=0&&u>i&&v>i){
			int p=num[i].x,q=num[u].x;
			dp[i][4]+=min(num[i].x,num[u].x)+f;
			num[i].x-=min(num[i].x,num[u].x),num[u].x-=min(num[i].x,num[u].x);
			dp[i][4]+=min(num[i].x,num[v].x);
			num[i].x=p,num[u].x=q;
		}
		
		if(u!=0&&u>i&&v>i){
			int p=num[i].x,q=num[v].x;
			dp[i][5]+=min(num[i].x,num[v].x)+f;
			num[i].x-=min(num[i].x,num[v].x),num[v].x-=min(num[i].x,num[v].x);
			dp[i][5]+=min(num[i].x,num[u].x);
			num[i].x=p,num[v].x=q;
		}
		dp[i][3]=f;
		f=max(dp[i][1],max(dp[i][2],max(dp[i][4],dp[i][5])));
	}
	cout<<f;
	
	
	
	return 0;
}