Untitled
raw download clone
C
views 55
,
size 1222 b
#include<stdio.h>
int *a,*b,*pos;
int cmp(const void *x,const void *y)
{
     int *vx = (const int *) x;
     int *vy = (const int *) y;
     if(a[*vx]-b[*vx]>a[*vy]-b[*vy])return 1;
     if(a[*vx]-b[*vx]<a[*vy]-b[*vy])return -1;
     return 0;
}

int main(void)
{
     int n,k,i,j;
     unsigned long long sum=0;
     scanf("%d%d\n",&n,&k);

     a=(int*)malloc(n*sizeof(int));
     b=(int*)malloc(n*sizeof(int));
     pos=(int*)malloc(n*sizeof(int));
     for(i=0;i<n;i++)
     {
          scanf("%d",a+i);
          pos[i]=i;
     }
     for(i=0;i<n;i++)
     {
          scanf("%d",b+i);
     }
     qsort(pos,n,sizeof(int),cmp);
     /*for(i=1;i<n;i++)//insertion sort (TLE)
     {
          int tmp=pos[i];
          j=i;
          while(j>0&&a[pos[j-1]]-b[pos[j-1]]>a[tmp]-b[tmp])
          {
               pos[j]=pos[j-1];
               j--;
          }
          pos[j]=tmp;
     }*/

     for(i=0;i<k;i++)
     {
          sum+=a[pos[i]];
     }
     for(i=k;i<n;i++)
     {
          if(a[pos[i]]<=b[pos[i]])sum+=a[pos[i]];
          else sum+=b[pos[i]];
     }
     printf("%lld\n",sum);

     free(a);
     free(b);
     free(pos);
     return 0;
}
close fullscreen
Login or Register to edit or fork this paste. It's free.