吉林区域赛 I - Strength

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node{
 4     int s,t;
 5 }a[100005];
 6 int b[100005];
 7 int vis[100005];
 8 int cmp(node x,node y){
 9     return x.s<y.s;
10 }
11 int main(){
12     int T;
13     scanf("%d",&T);
14     for(int j=1;j<=T;j++){
15         memset(vis,0,sizeof(vis));
16         int n,m;
17         scanf("%d%d",&n,&m);
18         for(int i=0;i<n;i++)
19             scanf("%d",&b[i]);
20         for(int i=0;i<m;i++)
21             scanf("%d",&a[i].s);
22         for(int i=0;i<m;i++)
23             scanf("%d",&a[i].t);
24         sort(a,a+m,cmp);
25         sort(b,b+n);
26         long long ans1=0,ans2=0;
27         int l=0,r=0;
28         while(l<n&&r<m){
29             if(b[l]>=a[r].s){
30                 if(a[r].t==0){
31                     ans1+=b[l]-a[r].s;
32                 }
33                 vis[l]=1;
34                 l++;
35                 r++;
36             }
37             else l++;
38         }
39         if(r==m){
40             for(int i=0;i<n;i++)
41                 if(!vis[i])
42                     ans1+=b[i];
43         }
44         else{
45             l=0,r=n-1;
46             while(r>=0&&l<m){
47                 if(b[r]>=a[l].s&&a[l].t==0){
48                     ans2+=b[r]-a[l].s;
49                     r--;
50                     l++;
51                 }
52                 else l++;
53             }
54         }
55         printf("Case %d: %lld\n",j,max(ans1,ans2));
56     }
57 }