Cod sursa(job #141525)

Utilizator BuniakovskiNeguletu Octavian Buniakovski Data 23 februarie 2008 12:49:18
Problema Elimin Scor 90
Compilator c Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<stdio.h>   
long int n,m,r,c,i,j,a[32][4096],aux,doila[32],max,cod,nbit[65536],   
lin,col,s[4096],sc,sol,max1;   
void heapdown(long int ic,long int nc);   
void swap(long int i1,long int i2);   
int main()   
{   
    FILE *f,*g;f=fopen("elimin.in","r");g=fopen("elimin.out","w");   
    fscanf(f,"%ld%ld%ld%ld",&m,&n,&r,&c);   
    if(m<=n)for(i=0;i<m;i++)for(j=0;j<n;j++)fscanf(f,"%ld",&a[i][j]);   
    else   
    { for(i=0;i<m;i++)for(j=0;j<n;j++)fscanf(f,"%ld",&a[j][i]);   
      aux=m;m=n;n=aux;aux=r;r=c;c=aux;   
    }   
    if(r==0)   
    { for(i=0;i<m;i++)   
       for(j=0;j<n;j++)   
        s[j+1]+=a[i][j];   
      for(i=n/2;i>=1;i--)heapdown(i,n);   
      for(i=n;i>=c;i--){swap(1,i);heapdown(1,i-1);}   
      sol=0;   
      for(i=c+1;i<=n;i++) sol+=s[i];   
      fprintf(g,"%ld\n",sol);   
      fcloseall();   
      return 0;   
    }   
    doila[0]=1;   
    for(i=1;i<=m;i++)doila[i]=doila[i-1]<<1;   
    max=doila[m];max1=doila[m-1];   
    for(cod=0;cod<max1;cod++)   
    {nbit[cod<<1]=nbit[cod];nbit[(cod<<1)|1]=nbit[cod]+1;}   
    for(cod=0;cod<max;cod++)   
    { if(nbit[cod]==r)   
      { for(lin=0;lin<m;lin++)   
          if(!(cod&doila[lin]))   
           for(col=0;col<n;col++)s[col+1]+=a[lin][col];   
        for(i=n/2;i>=1;i--)heapdown(i,n);   
        for(i=n;i>=c;i--){swap(1,i);heapdown(1,i-1);}   
        sc=0;   
        for(i=1;i<=c;i++) s[i]=0;   
        for(i=c+1;i<=n;i++) {sc+=s[i];s[i]=0;}   
        if(sc>sol)sol=sc;   
      }   
    }   
    fprintf(g,"%ld\n",sol);   
    fcloseall();   
    return 0;   
}   
void swap(long int i1,long int i2)   
{   
    aux=s[i1];s[i1]=s[i2];s[i2]=aux;   
}   
void heapdown(long int ic,long int nc)   
{   
    long int is,is1;   
    is=ic<<1;is1=is+1;   
    if(is>nc)return;   
    if(is<nc)if(s[is]<s[is1])is=is1;   
    if(s[ic]<s[is]){swap(is,ic);heapdown(is,nc);}   
}