Cod sursa(job #271872)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 6 martie 2009 00:14:25
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define max(a,b) (a>b?a:b)
using namespace std;

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

int A[20][600],l,c,N,M,sum[600];
int rez;

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

int calc(int conf){

    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];

    sort(sum+1,sum+M+1);

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


    int Nh=M;
    while(Nh>1){
        swap(1,Nh);
        --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);
            i=j;
        }
    }
*/
    int s=0;
    /*for(int i=M;i>c;--i)
        s+=sum[i];*/
    for(int i=c+1;i<=M;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;
}