Cod sursa(job #318865)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 29 mai 2009 19:23:20
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<stdio.h>   
#include<algorithm>   
  
using namespace std;   
  
#define IN "elimin.in","r",stdin   
#define OUT "elimin.out","w",stdout   
#define Nmax 1007
#define Max 21   
  
int n,m,r,c,rez;   
int v[Nmax][Max];   
int sol[Max],viz[Max],sum[Max];   
  
void citire()   
{   
    int aux;   
    int nr;   
    freopen(IN);   
    scanf("%d%d%d%d",&m,&n,&r,&c);   
    if(n>m)   
    {   
        for(int i=1;i<=m;++i)   
            for(int j=1;j<=n;++j)   
            {   
                scanf("%d",&nr);   
                v[j][m-i+1]=nr;   
            }   
        aux=n;   
        n=m;   
        m=aux;   
        aux=r;   
        r=c;   
        c=aux;   
    }   
    else    
        for(int i=1;i<=m;++i)   
            for(int j=1;j<=n;++j)   
                scanf("%d",&v[i][j]);   
}   
void back(int k)   
{   
    int best;   
    if(k==c+1)   
    {   
        best=0;   
        for(int i=1;i<=m;++i)   
            sum[i]=0;   
        for(int i=1;i<=m;++i)   
            for(int j=1;j<=n;++j)   
                if(viz[j]==0)   
                    sum[i]+=v[i][j];   
        sort(sum+1,sum+m+1);   
        for(int i=r+1;i<=m;++i)   
            best+=sum[i];          
        if(best>rez)   
            rez=best;   
        return;   
    }   
    for(int i=sol[k-1]+1;i<=n-(c-k);++i)   
    {   
        sol[k]=i;   
        viz[i]=1;   
        back(k+1);   
        viz[i]=0;   
    }   
}   
int main()   
{   
    freopen(OUT);   
    citire();   
    back(1);   
    printf("%d\n",rez);   
    return 0;   
}