Cod sursa(job #17540)

Utilizator supernovaMihai Pantis supernova Data 16 februarie 2007 10:47:47
Problema Elimin Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <stdio.h>
#include <vector>

using namespace std;

int a[50][10000],sum,n,m,n1,m1;
vector <int> s;
int s[10000];

void citire(void)
{
    int i,j,aux;
    FILE *f=fopen("elimin.in","r");
    
    fscanf(f,"%d %d",&n, &m, &n1, &m1);
    for(i=0;i<n;i++)
	for(j=0;j<m;j++) fscanf(f,"%d",&a[i][j]);
    
    sum=0;
    if(n>m)
    {
	aux=n;n=m;m=aux;
	aux=n1;n1=m1;m1=aux;
	for(j=0;j<n;j++)
	    for(i=0;i<m;i++) { fscanf(f,"%d",&a[i][j]); sum+=a[i][j]; }
    }
	  
    else
    {
	for(i=0;i<n;i++)
	    for(j=0;j<m;j++) { fscanf(f,"%d",&a[i][j]);sum+=a[i][j]; }
    }  

}

void output(int best)
{
    FILE *f=fopen("elimin.out","w");
    fprintf(f,"%d\n",best);
    fclose(f);
}

int main(void)
{
    int b[20],i,j,removed,sum0,best=-999999999;

    for(i=0;i<20;i++) b[i]=0;
    while(b[0]>1)
    {
	removed=0;sum0=sum;
	for(i=0;i<n;i++) if(b[i]==1) removed++;
	if(removed==n1)
	{
	    for(i=0;i<n;i++)    
		if(b[i]==1)
		    for(j=0;j<m;j++) sum0-=a[i][j];
	    s.resize(0);s.resize(m);
	    for(i=0;i<m;i++)
	    {
		for(j=0;j<n;j++) if(b[j]==0) s[i]+=b[j];
	    }
	    sort(s.begin(),s.end());
	    for(i=0;i<m1;i++) sum0-=s[i];
	    if(sum0>best) best=sum0;
	}

	b[n-1]++;
	for(i=n-1;i>0;i--) if(b[i]>1) { b[i]=0;b[i-1]++; }
    }
    
    output(best);
    return 0;
}