（技巧）AtCoder Grand Contest 018 C : Coins-白红宇

（技巧）AtCoder Grand Contest 018 C : Coins

阅读量：4448 次

发布时间：2019-06-07

本文共 3246 字，大约阅读时间需要 10 分钟。

Problem Statement

There are X+Y+Z people, conveniently numbered 1 through X+Y+Z. Person i has Ai gold coins, Bi silver coins and Ci bronze coins.

Snuke is thinking of getting gold coins from X of those people, silver coins from Y of the people and bronze coins from Z of the people. It is not possible to get two or more different colors of coins from a single person. On the other hand, a person will give all of his/her coins of the color specified by Snuke.

Snuke would like to maximize the total number of coins of all colors he gets. Find the maximum possible number of coins.

Constraints

1≤X

1≤Y

1≤Z

X+Y+Z≤105

1≤Ai≤109

1≤Bi≤109

1≤Ci≤109

Input

Input is given from Standard Input in the following format:

X Y ZA1 B1 C1A2 B2 C2:AX+Y+Z BX+Y+Z CX+Y+Z

Output

Print the maximum possible total number of coins of all colors he gets.

Sample Input 1

Copy

1 2 12 4 43 2 17 6 75 2 3

Sample Output 1

Copy

Get silver coins from Person 1, silver coins from Person 2, bronze coins from Person 3 and gold coins from Person 4. In this case, the total number of coins will be 4+2+7+5=18. It is not possible to get 19 or more coins, and the answer is therefore 18.

Sample Input 2

Copy

3 3 216 17 12 7 52 16 1217 7 713 2 1012 18 316 15 195 6 2

Sample Output 2

Copy

Sample Input 3

Copy

6 2 433189 87907 27734974271616 46764 5753065208801 53151 32716125158589 4337 79669768666854 17565 28991058350598 35195 47811268913919 88414 1039624557953 69657 69925375244255 98144 4684437092332 42580 75243709739752 19060 84506286960126 74101 382963164

Sample Output 3

Copy

3093929975

用（ai-ci,bi-ci，0）替换（ai,bi,ci）的想法非常精彩。排序时的考虑也值得思考。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #define mp make_pair14 #define MIN(a,b) (a>b?b:a)15 //#define MAX(a,b) (a>b?a:b)16 typedef long long ll;17 typedef unsigned long long ull;18 const int MAX=1e5+5;19 const int INF=1e8+5;20 using namespace std;21 //const int MOD=1e9+7;22 typedef pair
                  
                    pii;23 const double eps=0.00000001;24 struct node25 {26 ll a,b;27 }re[MAX];28 bool cmp(node x,node y)29 {30 if(x.a-x.b!=y.a-y.b)31 return x.a-x.b
                   
                    y.b;34 }35 ll x,y,z;36 ll gold[MAX],silver[MAX];37 ll sum,gsum,ssum;38 priority_queue
                    
                      g,s;39 int main()40 {41 scanf("%lld%lld%lld",&x,&y,&z);42 ll num=x+y+z;43 ll p,q,r;44 for(ll i=1;i<=num;i++)45 {46 scanf("%lld%lld%lld",&p,&q,&r);47 re[i].a=p-r;re[i].b=q-r;48 sum+=r;49 }50 sort(re+1,re+1+num,cmp);51 ssum=gsum=0LL;52 for(ll i=x+y+z;i>=y+z+1;i--)53 {54 g.push(-re[i].a);55 gsum+=re[i].a;56 }57 gold[x]=gsum;58 for(ll i=y+z;i>y;i--)59 {60 g.push(-re[i].a);61 gsum+=re[i].a;62 gsum+=g.top();63 gold[x+y+z-i+1]=gsum;64 g.pop();65 }66 for(ll i=1;i<=y;i++)67 {68 s.push(-re[i].b);69 ssum+=re[i].b;70 }71 silver[y]=ssum;72 for(ll i=y+1;i<=y+z;i++)73 {74 s.push(-re[i].b);75 ssum+=re[i].b;76 ssum+=s.top();77 silver[i]=ssum;78 s.pop();79 }80 ll an;81 for(ll i=y;i<=y+z;i++)82 {83 if(i!=y)84 an=max(an,silver[i]+gold[x+y+z-i]);85 else86 an=silver[i]+gold[x+y+z-i];87 }88 printf("%lld\n",an+sum);89 return 0;90 }

转载于:https://www.cnblogs.com/quintessence/p/7226763.html

你可能感兴趣的文章