[AGC018C] Coins

Description

(n) 个物品，每个有三种属性，每种属性有一个权值，现在要选 (x) 个 (A) 属性，(y) 个 (B) 属性，(z) 个 (C) 属性，(x+y+z=n)，使得权值和最大。

Solution

首先每种物品必须选一个属性，不妨钦定全选 (A)。那么把 (B) 和 (C) 改成 (B-A) 和 (C-A)，记为 (A') 和 (B')，就转换为只有两种属性的问题了。

钦定一种选物品的方案，要想在此基础上更优，也就是存在 (B_i'+C_jgeq B_j'+C_i')，移项得到 (B_i'-C_i'geq B_j'-C_j')。所以按照 (B-C) 排序后，一种方案一定可以通过交换使得选 (B) 的是一个前缀，选 (C) 的是一个后缀，而答案不会更劣反而更优。预处理出前缀选 (B) 和后缀选 (C) 的答案即可。

#include<stdio.h>
#include<algorithm>
#include<queue> 
using namespace std;

inline int read(){
    int x=0,flag=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
    return flag? x:-x;
}

const int N=1e5+7;

typedef long long ll;

struct Node{
    ll x,y;
    bool operator <(const Node &X) const{
        return x-y>X.x-X.y;
    }
}t[N];

priority_queue<ll> Q;
ll pre[N],suf[N];

int main(){
    freopen("collection.in","r",stdin);
    freopen("collection.out","w",stdout);
    int R=read(),Y=read(),G=read(),n=R+Y+G;
    ll ans=0;
    for(int i=1;i<=n;i++){
        int a=read(),b=read(),c=read();
        t[i].x=b-a,t[i].y=c-a; ans+=a;
    }
    sort(t+1,t+1+n); ll now=0;
    for(int i=1;i<=n;i++){
        Q.push(-t[i].x); now+=t[i].x;
        if(i>Y) now+=Q.top(),Q.pop();
        pre[i]=now;
    }
    while(!Q.empty()) Q.pop(); now=0;
    for(int i=n;i;i--){
        Q.push(-t[i].y); now+=t[i].y;
        if(i<=n-G) now+=Q.top(),Q.pop();
        suf[i]=now;
    }
    ll ret=-1e18;
    for(int i=Y;i<=n-G;i++)
        ret=max(ret,pre[i]+suf[i+1]);
    printf("%lld",ans+ret);
}