Cod sursa(job #1010087)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 14 octombrie 2013 11:40:14
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <algorithm>
#include <string.h>
#define Nmax 8000
using namespace std;
ifstream f("elimin.in");
ofstream g("elimin.out");

int N,M,R,C,a[Nmax][Nmax],st[Nmax],used[Nmax],S,Slin[Nmax];

inline void ReadInput()
{
    f>>M>>N>>R>>C;
    if(M>=N)
    {
        for(int i=1;i<=M;++i)
            for(int j=1;j<=N;++j)f>>a[i][j],Slin[i]+=a[i][j];
    }
    else //if(M<N) fac coloanele linii
    {
        for(int i=1;i<=M;++i)
            for(int j=1;j<=N;++j)f>>a[j][i],Slin[j]+=a[j][i];
        swap(M,N);
        swap(R,C);
    }
    //for(int i=1;i<=M;++i,g<<'\n')
        //for(int j=1;j<=N;++j)g<<a[i][j]<<' ';
}

inline void Print(int st[])
{
    int sum[Nmax];
    memcpy(sum,Slin,sizeof(Slin));
    for(int j=1;j<=C;++j)
            for(int i=1;i<=M;++i)sum[i]-=a[i][st[j]];
    sort(sum+1,sum+1+M);
    int sol=0;
    for(int i=R+1;i<=M;++i)sol+=sum[i];
    if(sol>S)S=sol;

}
void Back(int k)
{
    if(k==C+1){Print(st);return;}
    for(int i=st[k-1]+1;i<=N;++i)
        if(!used[i])
        {
            st[k]=i; used[i]=1;
            Back(k+1);
            used[i]=0;
        }
}
int main()
{
    ReadInput();
    Back(1);
    g<<S<<'\n';
    f.close();g.close();
    return 0;
}