CF1467C Three Bags

Description

You are given three bags. Each bag contains a non-empty multiset of numbers. You can perform a number of operations on these bags. In one operation, you can choose any two non-empty bags, and choose one number from each of the bags. Let's say that you choose number $a$ from the first bag and number $b$ from the second bag. Then, you remove $b$ from the second bag and replace $a$ with $a-b$ in the first bag. Note that if there are multiple occurrences of these numbers, then you shall only remove/replace exactly one occurrence.

You have to perform these operations in such a way that you have exactly one number remaining in exactly one of the bags (the other two bags being empty). It can be shown that you can always apply these operations to receive such a configuration in the end. Among all these configurations, find the one which has the maximum number left in the end.

Solution

将数$a$向另一个数$b$连边当$a$被移除而$b$变为$b-a$

那么就会形成一棵所有边指向根的树（只操作$n-1$次所以会连接$n-1$条边）

发现所有奇数层在答案中都被减去，偶数层都被加上（根的深度为$0$）

那么这棵树合法当且仅当满足以下之一

奇数层的点至少包含来自两个集合的数
奇数层的点包含来自同一集合的全部数

只有如此才可以按照规则合法地连边

对这两种情况分别讨论即可

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n1,n2,n3;
long long a1[300005],a2[300005],a3[300005],s1,s2,s3,ans,min1=1ll<<60,min2=1ll<<60,min3=1ll<<60,s;
inline int read(){
    int w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar();
    return w*f;
}
int main(){
    n1=read(),n2=read(),n3=read();
    for(int i=1;i<=n1;i++)a1[i]=read(),s1+=a1[i],min1=min(min1,a1[i]);
    for(int i=1;i<=n2;i++)a2[i]=read(),s2+=a2[i],min2=min(min2,a2[i]);
    for(int i=1;i<=n3;i++)a3[i]=read(),s3+=a3[i],min3=min(min3,a3[i]);
    s=s1+s2+s3,printf("%I64d
",max(s-min1*2-min2*2,max(s-min1*2-min3*2,max(s-min2*2-min3*2,max(s1+s2-s3,max(s1+s3-s2,s2+s3-s1))))));
    return 0;
}

Three Bags