Cod sursa(job #9085)

Utilizator georgianaGane Andreea georgiana Data 26 ianuarie 2007 17:17:28
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <stdio.h>

int m,n,r,c,v[15][4000],s[15],nr,smax,sum[4000];

void qSort(int st,int dr)
{
     int i=st, j=dr, m=sum[(i+j)/2];
     do
     {
         while (sum[i]<m) i++;
         while (sum[j]>m) j--;
         if (i<=j)
         {
             int aux=sum[i]; sum[i]=sum[j]; sum[j]=aux;
             i++; j--;         
         }
     } 
     while (i<=j);
     if (st<j) qSort(st,j);
     if (i<dr) qSort(i,dr);
}

void sol()
{
    for (int i=0;i<n;i++)
    {
        sum[i]=0;
        for (int j=0;j<m;j++)
             if (s[j]==1) sum[i]+=v[j][i];
    }
    qSort(0,n-1);
    int aux=0;
    for (int i=c;i<n;i++) aux+=sum[i];
    if (aux>smax) smax=aux;
}

void back(int k)
{
    if (nr==r) sol();
    else if (k<m)
             for (int i=0;i<2;i++)
             {
                 s[k]=i;
                 nr+=i;
                 back(k+1);
                 nr-=i;
                 s[k]=0;
             }
}

int main()
{
    freopen("elimin.in","r",stdin);
    scanf("%d %d %d %d",&m,&n,&r,&c);
    if (m<=n)
        for (int i=0;i<m;i++)
             for (int j=0;j<n;j++)
                  scanf("%d",&v[i][j]);
    else {
            for (int i=0;i<m;i++)
                 for (int j=0;j<n;j++)
                      scanf("%d",&v[j][i]);
            int aux=m; m=n; n=aux;
                aux=r; r=c; c=aux;
         }
    
    r=m-r;
    smax=-1;
    nr=0;
    back(0);
    
    freopen("elimin.out","w",stdout);
    printf("%d\n",smax);
    fclose(stdout);
    return 0;
}