Cod sursa(job #271851)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 5 martie 2009 23:47:39
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include<stdio.h>
#define max(a,b) (a>b?a:b)

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

int A[1000][1000],l,c,N,M;
int rez;

void swap(int i,int j,int sum[1000]){
    sum[i]^=sum[j];sum[j]^=sum[i];sum[i]^=sum[j];
}

int calc(int conf){
    int sum[1000];
    for(int i=1;i<=M;i++)
        sum[i]=0;
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            if( !( (1<<(i-1))&conf) )
                sum[j]+=A[i][j];

    for(int i=1;i<=M;i++){
        int j=i;
        while(j/2 && sum[j]>sum[j/2]){
            swap(j,j/2,sum);
            j/=2;
        }
    }


    int Nh=M;
    while(Nh>1){
        swap(1,Nh,sum);
        --Nh;
        int i=1,j;
        while(1){
            j=i*2;
            if(j>Nh) break;
            if(j+1<=Nh && sum[j+1]>sum[j]) ++j;
            if(sum[i]>sum[j]) break;
            swap(j,i,sum);
            i=j;
        }
    }

    int s=0;
    for(int i=M;i>c;--i)
        s+=sum[i];
    return s;

}

int main(){
    fscanf(fin,"%d %d %d %d",&N,&M,&l,&c);
    if(N<M)
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
            fscanf(fin,"%d",&A[i][j]);
    else{
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                fscanf(fin,"%d",&A[j][i]);
        N^=M;M^=N;N^=M;
        l^=c;c^=l;l^=c;
    }

    for(int i=0;i<(1<<N);++i){
        int nr=0,x=i;
        while(x){
            nr+=x%2;
            x/=2;
        }
        int s=0;
        if(nr==l)
            s=calc(i);
        rez=max(rez,s);

    }

    fprintf(fout,"%d\n",rez);
    fclose(fin);
    fclose(fout);
    return 0;
}