Cod sursa(job #79480)

Utilizator FlorianFlorian Marcu Florian Data 22 august 2007 17:55:43
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
FILE*f=fopen("elimin.in","r");
FILE*g=fopen("elimin.out","w");
int b[500][500],st[100],n,m,R,C,a[500][500];
long Max=-1000000,s[1000],sum;
void read()
        {
        int aux,i,j;
	fscanf(f,"%ld %ld %ld %ld",&n,&m,&R,&C);
	for(i=1;i<=n;++i) for(j=1;j<=m;++j) fscanf(f,"%ld",&a[i][j]),sum+=a[i][j];
        if(n>m)
                {
                for(i=1;i<=m;++i)
                        for(j=1;j<=n;++j)
                        b[i][j]=a[n-j+1][i];
                aux=n; n=m; m=aux;
                aux=R; R=C; C=aux;
                }
        }
int stiva(int n)
	{
	int p=0,nr=0;
	memset(st,0,sizeof(st));
	while(n)
		{
		st[++p]=n%2;
		if(n%2==1) nr++;
		n/=2;
		}
	return nr;
	 }
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<=m;++i)
		for(j=1;j<=n;++j)
			if(st[j]==0) s[i-1]+=b[j][i];
			else S+=b[j][i];
	qsort(s,n,sizeof(s[0]),cmp);
	for(i=0;i<C;++i) S+=s[i];
	Max=sum-S>Max?sum-S:Max;
	}



void solve()
	{
	int i;
	for(i=1;i<=pow(2,(n-1));++i)
		{
		if(stiva(i)==R)
			{ calcul();}

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