AGC018C Coins

atcoder
(老版atcoder和新版的访问速度不是一个级别的（划掉)

这个题一个很关键的点：只考虑\(x,y\),不考虑\(z\)

我们假设\(i\)选择\(A_i\),\(j\)选择\(B_j\)比两者交换选择时更优,则有\(A_i+B_j>A_j+B_i\),移项得\(A_i-B_i>A_j-B_j\).做到这里一个显然的贪心就出来了：我们将所有的人按照\(A_i-B_i\)从大到小排序,前\(x\)个人选择\(A_i\),剩下的\(y\)个人选择\(B_i\)即为最优决策

那么现在再来考虑\(z\)的情况,首先继续按照\(A_i-B_i\)排序,那么同样不会存在排在前面的选择\(B_i\)同时排在后面的选择了\(A_i\)的情况,因此必然存在一个分界点使得分界点之前的一段不会出现\(B_i\),分界点之后的一段不会出现\(A_i\).再考虑\(C_i\)就会发现这两段分别是与最开始相同的问题,我们对每个子问题开一个堆,同时在枚举分界点的过程中维护当前所选择的\(A_i\)或者是\(B_i\)即可,具体过程可以参照下面的代码

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=10000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct pnode{int a,b,c;}p[300100];
bool operator <(pnode p,pnode q) {return p.a-p.b>q.a-q.b;}
struct node{int a,b;};
bool operator <(node p,node q) {return p.a-p.b>q.a-q.b;}
priority_queue<node> q;
int n,na,nb,nc;
ll f[300300],g[300300];

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int main()
{
    na=read();nb=read();nc=read();n=na+nb+nc;
    rep(i,1,n) 
    {
        p[i].a=read();p[i].b=read();p[i].c=read();
    }
    sort(p+1,p+1+n);
    //rep(i,1,n) cout << p[i].a << " " << p[i].b << " " << p[i].c << endl;
    ll sum=0;
    rep(i,1,na) 
    {
        node tmp;
        tmp.a=p[i].a;tmp.b=p[i].c;
        q.push(tmp);sum+=p[i].a;
    }
    f[na]=sum;
    rep(i,na+1,na+nc)
    {
        node now=q.top();
        if (now.a-now.b<p[i].a-p[i].c)
        {
            sum-=now.a;sum+=now.b;
            q.pop();
            node tmp;
            tmp.a=p[i].a;tmp.b=p[i].c;sum+=p[i].a;
            q.push(tmp);
        }
        else sum+=p[i].c;
        f[i]=sum;
    }
    sum=0;
    while (!q.empty()) q.pop();
    //rep(i,1,n) cout << f[i] << " ";cout << endl;
    per(i,n,n-nb+1)
    {
        node tmp;
        tmp.a=p[i].b;tmp.b=p[i].c;
        q.push(tmp);sum+=p[i].b;
    }
    g[n-nb+1]=sum;
    per(i,n-nb,na+1)
    {
        node now=q.top();
        //cout << now.a << " " << now.b << endl;
        if (now.a-now.b<p[i].b-p[i].c)
        {
            sum-=now.a;sum+=now.b;
            q.pop();
            node tmp;
            tmp.a=p[i].b;tmp.b=p[i].c;sum+=p[i].b;
            q.push(tmp);
        }
        else sum+=p[i].c;
        g[i]=sum;
    }
    ll ans=0;
    //rep(i,1,n) cout << g[i] << " ";cout << endl;
    rep(i,na,n-nb+1) ans=max(ans,f[i]+g[i+1]);
    printf("%lld",ans);
    return 0;
}