Cod sursa(job #8077)

Utilizator mariusdrgdragus marius mariusdrg Data 23 ianuarie 2007 19:50:38
Problema Elimin Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.3 kb
#include<stdio.h>
#include<algorithm>


using namespace std;

const int maxn = 30010;
const int maxn2 = 30;

int aux[maxn];

int ind[maxn];
int m;
int maxi;
int c;
int sl[maxn];
short a[maxn2][maxn];
int sc[maxn];
int i;
int lim;
int ver;
int n;
int j;
int a1[maxn];
int nr1;
int r;


bool cmpf1(const int &a,const int &b)
{
        return aux[a]<aux[b];
}

void bkt(int i)
{
        if (i<=lim)
        {
                for(a1[i]=0;a1[i]<=1;a1[i]++)
                {
                        if (a1[i]==1) nr1++;
                        bkt(i+1);
                        if (a1[i]==1) nr1--;
                }
        }
        else
        {
                if (ver==1)
                {
                        if (nr1!=r)  return ;
                        int i1;
                        int sol=0;
                        memcpy(aux,sc,sizeof(sc));
                        for(i1=1;i1<=lim;i1++)
                        {
                                if (a1[i1]==1)
                                {
                                        for(j=1;j<=m;j++)
                                        {
                                                ind[j]=j;
                                                aux[j]-=a[i1][j];
                                        }
                                }
                        }
                        sort(ind+1,ind+m+1,cmpf1);
                        for(i1=1;i1<=n;i1++)
                        {
                                if (a1[i1]==0) sol+=sl[i1];
                        }
                        for(i1=1;i1<=c;i1++)
                        {
                                int i2=ind[i1];
                                for(j=1;j<=n;j++)
                                        if (a1[j]==0)sol-=a[j][i2];
           
                        }
                        if (sol>maxi)
                        {
                                maxi=sol;
                        }
                
                }
                else
                {
                        if (nr1!=c)  return ;
               
                        int i1;
                        int sol=0;
                        memcpy(aux,sl,sizeof(sl));
                        for(i1=1;i1<=lim;i1++)
                        {
                                if (a1[i1]==1)
                                {
                                        for(j=1;j<=n;j++)
                                        {
                                                ind[j]=j;
                                                aux[j]-=a[j][i1];
                                        }
                                }
                        }
                        sort(ind+1,ind+n+1,cmpf1);
                        for(i1=1;i1<=m;i1++)
                        {
                                if (a1[i1]==0) sol+=sc[i1];
                        }
                        for(i1=1;i1<=r;i1++)
                        {
                                int i2=ind[i1];
                                for(j=1;j<=m;j++)
                                        if (a1[j]==0)sol-=a[i2][j];
                        }
                        if (sol>maxi) maxi=sol;
                }
        }

}



int main()
{
        freopen("elimin.in","r",stdin);
        freopen("elimin.out","w",stdout);
        scanf("%d %d %d %d",&n,&m,&r,&c);
        if (n<m)
        {
                ver=1;
                lim=n;
                for(i=1;i<=n;i++)
                        for(j=1;j<=m;j++)
                        {
                                scanf("%hd",&a[i][j]);
                                sc[j]+=a[i][j];
                                sl[i]+=a[i][j];
                        }

        }
        else
        {
                ver=1;
                lim=n;
                for(i=1;i<=n;i++)
                        for(j=1;j<=m;j++)
                        {
                                scanf("%hd",&a[j][i]);
                                sc[i]+=a[j][i];
                                sl[j]+=a[j][i];
                        }
                int aux=n;
                n=m;
                m=aux;

        }
      

        bkt(1);

        printf("%d",maxi);

        return 0;
}