COLOURED ARRAY

Description:

"Chef had a hard time arguing with his friend, and after getting a great old kick Chef saw a colored array with N cells, numbered from 1 to N. Explanation: For this sample, we can repaint only once, since K = 1. We should repaint 4th cell with color 1. We will pay 1 for this, and receive: 1 (1st cell - 1st color) + 1 (2nd cell -1st color) + 1 (3rd cell - 2nd color) + 3 (4th cell - 1st color) = 6. Hence we get 6 1 = 5 points in total, and it is the optimal answer. The kick was so strong that Chef suddenly understood the rules of the game. Each cell is painted with a color. Here the colors are numbered from 1 to M. For any cell i, Chef can repaint it with any color q, and the cost of such operation is Ci,q points. However Chef can do at most K repaintings (0 repaintings is possible). After performing all repaintings, each cell will have some color. For each cell i, if cell i has color q then Chef will receive Bi,q points. Now Chef is wondering how many points can he receive in total when he repaints optimally. Input The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains three space-separated integers N, M and K, denoting the number of cells and the number of colors, the maximal possible number of repaintings respectively. The next line contains N space-separated integers A1, A2, ..., AN, denoting the initial colors of the cells. Then N lines follow. The ith line of them contains M integers Bi1, Bi2, ..., BiM, where Bij denotes how many points Chef will receive if the cell i will be painted with j-th color after all operations. Then N lines follow. The ith line of them contains M integers Ci1, Ci2, ..., CiM, where Cij denotes how many points Chef will lose if he repaints the cell i with color j. Note: Be careful that the size of input files can be large. Output For each test case, output a single line containing the maximal possible points. Constraints 1 <= T<= 5 0 <= K <= 1000 1 <= N, M <= 1000 1<= Ai<= M 0

Program :

  • #include <stdio.h>
    #include<stdlib.h>
    int main()
    {
      int cases,n,m,k,i,j;
      int col[1001],cost[1001][1001],points[1001][1001];
      scanf("%d",&cases);
      while(cases--)
      {
        scanf("%d %d %d",&n,&m,&k);
        int max[n+1],pts[n+1],temp,x,tot=0;
        for(i=1;i<=n;i++)
          max[i]=0;
        for(i=1;i<=n;i++)
          scanf("%d",&col[i]);
        for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
            scanf("%d",&points[i][j]);
        for(i=1;i<=n;i++)
          for(j=1;j<=m;j++)
            scanf("%d",&cost[i][j]);
        for(i=1;i<=n;i++)
          pts[i]=points[i][col[i]];
        for(i=1;i<=n;i++)
        {
          for(j=1;j<=m;j++)
          {
            x=(points[i][j]-cost[i][j]);
            if(max[i]<(x-pts[i]))
              max[i]=x-pts[i];
          }
        }
        if(k>n)
          k=n;
        for(i=1;i<=k;i++)
        {
          for(j=i+1;j<=n;j++)
          {
            if(max[j]>max[i])
            {
              temp=max[i];
              max[i]=max[j];
              max[j]=temp;
              temp=pts[i];
              pts[i]=pts[j];
              pts[j]=temp;
            }
          }
          pts[i]=pts[i]+max[i];
        }
        for(i=1;i<=n;i++)
          tot+=pts[i];
        printf("%d",tot);
      }

    return 0;
    }