Cod sursa(job #17624)

Utilizator supernovaMihai Pantis supernova Data 16 februarie 2007 14:40:47
Problema Elimin Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <stdio.h>


int a[50][10000],sum,n,m,n1,m1;
int s[10000],ss[10000];

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

void output(int best)
{
    FILE *f=fopen("elimin.out","w");
    fprintf(f,"%d\n",best);
    fclose(f);
}
/*
void sort (int a[],int min, int max)
{
    int i,j,aux,med;
    
    
    for(i=0;i<n;i++)
	for(j=0;j<i;j++)
	    if(a[j]>a[i]) { aux=a[i];a[i]=a[j];a[j]=aux;}
}
*/

void _qsort (int a[], int left, int right)
{
    int s_left=left;
    int s_right=right;
    int pivot=a[left];
    
    while(left<right)
    {
	while((a[right]>=pivot) && (left<right))
	{
	    right--;
	}
	if(left!=right)
	{
	    a[left]=a[right];
	    left++;
	}
	while((a[left]<=pivot) && (left<right))
	{
	    left++;
	}
	if(left!=right)
	{
	    a[right]=a[left];
	    right--;
	}
     }
     a[left]=pivot;
     pivot=left;
     left=s_left;
     right=s_right;

     if(left<pivot) _qsort(a,left,pivot-1);
     if(right>pivot) _qsort(a,pivot+1,right);
}
    

int main(void)
{
    int b[20],i,j,removed,sum0,best=-999999999,pass;
    
    citire();
    int c[10]={3,4,1,88,9,-7,11,22,10,-5};
    _qsort(c,0,9);
    for(i=0;i<10;i++) printf("%d ",c[i]); printf("\n");
    
    
    for(i=0;i<n;i++)
    {
	ss[i]=0;
	for(j=0;j<m;j++) ss[i]+=a[i][j];
    }
    printf("%d %d %d %d %d\n",n,m,n1,m1,sum);
    for(i=0;i<20;i++) b[i]=0;
    while(b[0]<2)
    {
	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)
		    sum0-=ss[i];
	    if(sum0>=best)
	    {
  	      for(i=0;i<m;i++)
	      {	
	  	s[i]=0;
		for(j=0;j<n;j++) if(b[j]==0) s[i]+=a[j][i];
	      }
	      _qsort(s,0,m-1);
	      for(i=0;i<m1;i++) sum0-=s[i];
	      if(sum0>best) best=sum0;
	    }
	}
	pass=0;
	//for(i=0;i<n;i++) printf("%d ",b[i]); printf("\n");
	do
	{
	    b[n-1]++;
	    for(i=n-1;i>0;i--) if(b[i]>1) { b[i]=0;b[i-1]++; }
	    if(b[0]==2) pass=1;
	    removed=0;for(i=0;i<n;i++) 
	    {
		if(b[i]==1) removed++;
		if(removed>n1) break;
	    }
	    if(removed==n1) pass=1;
	} while (pass==0);
    }
    
    printf("%d\n",best);
    output(best);
    return 0;
}