Cod sursa(job #80043)

Utilizator FlorianFlorian Marcu Florian Data 25 august 2007 17:20:18
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<stdlib.h>
#include<math.h>
FILE*f=fopen("elimin.in","r");
FILE*g=fopen("elimin.out","w");
int st[2000],n,m,R,C,a[18][2000], b[18][1600],sl[2000],nrbiti[100000];
long Max=0,sum;
void precalc()
        {
        nrbiti[0]=0;
        nrbiti[1]=1;
        int i;
        for(i=1;i<=(1<<n);++i)
                {
                if(2*i<=(1<<n)) nrbiti[2*i]=nrbiti[i];
                if(2*i+1<=(1<<n)) nrbiti[2*i+1]=nrbiti[i]+1;
                }
        }
int s[2000];
void read()
        {
        int aux,i,j;
        fscanf(f,"%d %d %d %d",&n,&m,&R,&C);

        if(n<=m) for(i=1;i<=n;++i) for(j=1;j<=m;++j) fscanf(f,"%d",&a[i][j]),sum+=a[i][j],sl[i]+=a[i][j];
        if(n>m)
                {
                for(i=n;i>=1;--i)
                        for(j=1;j<=m;++j)
                        fscanf(f,"%d",&a[j][i]),sum+=a[j][i],sl[j]+=a[j][i];
                aux=n; n=m; m=aux;
                aux=R; R=C; C=aux;
                }
        }
void stiva(int n)
        {
        int p=0,nr=0;
        memset(st,0,sizeof(st));
        while(n!=0)
                {
                st[++p]=n&1;
                n=n>>1;
                }
         }
int cmp(const void*a, const void*b)
        {
        return *(int*)a-*(int*)b;
        }
void calcul()
        {
        int i,j,S=0,p=0;
        memset(s,0,sizeof(s));
        for(i=1;i<=n;++i)
              {
              if(st[i]==0) {
                         for(j=1;j<=m;++j)
                                s[j]+=a[i][j];

                         }
             else S+=sl[i];
              }
       // qsort(s,m,sizeof(s[0]),cmp);
        std::sort(s+1,s+m+1);
        for(i=1;i<=C;++i) S+=s[i];
        Max=sum-S>Max?sum-S:Max;
        }
void solve()
        {
        long long i,aa;
        aa=1<<n;
        for(i=0;i<aa;++i)
                {
                if(nrbiti[i]==R)
                        {
                        stiva(i);
                        calcul();
                        }


                }
       fprintf(g,"%ld",Max);
         }
int main()
        {
        read();
        precalc();
        solve();
        return 0;
        }