比赛 |
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;
}