Cod sursa(job #15053)

Utilizator vlad_popaVlad Popa vlad_popa Data 10 februarie 2007 16:44:13
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
using namespace std;

#include <cstdio>
#include <algorithm>

#define FIN "elimin.in"
#define FOUT "elimin.out"
#define NMAX 16

int s[NMAX], N, M, R, C, sol, sume[5001], a[16][5001], ct;

void checkit ()
{
  int i, j, rez;
  for (i = 1; i <= M; ++ i)
   {
     rez = 0;
     for (j = 1; j <= N; ++ j)
       if (!s[j])
         rez += a[i][j];
     sume[i] = rez;
   }
  sort (sume+1, sume+M+1);
  rez = 0;
  for (i = R+1; i <= M; ++ i)
    rez += sume[i];
  if (rez > sol)
    sol = rez;
}

void back (int p)
{
  for (int i = 0; i <= 1; ++ i)
   {
     s[p] = i;
     if (s[p])
       ct++;
     if (p == N)
       if (ct == C)
         checkit();
       else;
     else
       back (p + 1);
     if (s[p])
       ct--;
   }
}

int
 main ()
{
  int i, j, verif = 0;
  freopen (FIN, "rt", stdin);
  freopen (FOUT, "wt", stdout);

  scanf ("%d%d%d%d", &M, &N, &R, &C);
  if (N > M)
   {
     N ^= M;  M ^= N;  N ^= M;
     R ^= C;  C ^= R;  R ^= C;
     verif = 1;
   }
  for (i = 1; i <= M; ++ i)
    for (j = 1; j <= N; ++ j)
      if (!verif)
        scanf ("%d", &a[i][j]);
      else
        scanf ("%d", &a[j][i]);
  back (1);
  printf ("%d\n", sol);
  return 0;
}