Cod sursa(job #50094)

Utilizator chermanCorina Herman cherman Data 6 aprilie 2007 20:47:27
Problema Elimin Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <stdio.h>
#include <iostream>

FILE *in = fopen("elimin.in","r"), *out = fopen("elimin.out","w");

int n, m, r, c;
int a[600][600];
int eliminate[600] = {0};

int ss = 0;

int poz(int p, int u, int b[])
{
	int s=p, d=u, x=b[p];
	while ( s < d )
	{
		while ( b[d] >= x && s < d )
			--d;
		b[s] = b[d];
		while ( b[s] <= x && s < d )
			++s;
		b[d] = b[s];
	}
	b[s] = x;
	return s;
}

void qs(int p, int u, int b[])
{
	int m = poz(p, u, b);
	if ( p < m )
		qs(p, m-1, b);
	if ( m < u )
		qs(m+1, u, b);
}

void read()
{
    fscanf(in, "%d %d %d %d", &m, &n, &r, &c);

    for ( int i = 1; i <= m; ++i )
        for ( int j = 1; j <= n; ++j )
            fscanf(in, "%d" , &a[i][j]);
}

void suma()
{
    int t = 0;
    int b[600] = {0};

    for ( int i = 1; i <= m; ++i )
        for ( int j = 1; j <= n; ++j )
        {
            if ( eliminate[i] == 0 )
                b[j] += a[i][j];
        }

    qs(1, n, b);

    for ( int i = c+1; i <= n; ++i )
        t += b[i];

    if ( t > ss )
        ss = t;

    memset(eliminate, 0, sizeof(eliminate));
    //memset(b, 0, sizeof(b));

}

int x[600];

bool continuare(int k)
{
    bool t;
    t=true;
    for (int i=1;i<=k-1;i++)
      if (x[i]>=x[k])
      {
          t=false;
          break;
      }
   return t;
}
void bk(int xx, int yy )
{
    int k=1;
    bool vb;
    x[k]=0;
    while (k>0)
    {
     vb=false;
     while ((x[k]<xx) &&(vb==false))
     {
       x[k]=x[k]+1;
       vb=continuare(k);
     }
     if (vb)
       if (k==yy)
       {
            for ( int t = 1; t <= yy; ++t )
                eliminate[x[t]] = 1;

            suma();
       }
       else
       {
         k=k+1;
         x[k]=0;
       }
     else k=k-1;
     }
}


int main()
{
    read();

    bk(m,r);


    fprintf(out, "%d\n", ss);

	return 0;
}