Cod sursa(job #1471414)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 13 august 2015 20:23:43
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include<iostream>
#include<fstream>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

ifstream fin("elimin.in");
ofstream fout("elimin.out");

struct coord{
    int x,y;
};

int M,N,R,C,st[50],k;
int a[400][400],b[400][400],summax,sumafinala;

coord sum[400];

bool Cmp(const coord nr1, const coord nr2)
{
    return (nr1.x > nr2.x);
}

void Citire()
{
    int i,j;
    fin>>M>>N>>R>>C;
    for (i=1;i<=M;i++)
    {
        for (j=1;j<=N;j++)
            fin>>a[i][j];
    }
}

void Afisare1()
{
    int i,j,z;
    int x,suma,q;
    for (i=1;i<=k;i++)
    {
        x=st[i];
        for (j=1;j<=N;j++)
            b[i][j]=a[x][j];
    }

    for (j=1;j<=N;j++)
    {
        suma=0;
        for (i=1;i<=k;i++)
        {
            suma+=b[i][j];
        }
        sum[j].x=suma;
        sum[j].y=j;
    }

    sort (sum+1,sum+N+1, Cmp);

    q=N-C;
    sumafinala=0;

    for (i=1;i<=q;i++)
    {
        j=sum[i].y;

        for (z=1;z<=k;z++)
            sumafinala+=b[z][j];
    }
    summax=max(summax,sumafinala);
}

void Back1(int top, int k)
{
    int i,j;
    /// facem back pe linii
    /// combinari de n luate cate k unde k=M-R
    if (top==k+1) Afisare1();
    else
        for (i=st[top-1]+1;i<=M-k+top;i++)
    {
        st[top]=i;
        Back1(top+1,k);
    }
}

void Afisare2()
{
    int i,j,z;
    int x,suma,q;
    for (j=1;j<=k;j++)
    {
        x=st[j];
        for (i=1;i<=M;i++)
            b[i][j]=a[i][x];
    }

    for (i=1;i<=M;i++)
    {
        suma=0;
        for (j=1;j<=k;j++)
        {
            suma+=b[i][j];
        }
        sum[i].x=suma;
        sum[i].y=i;
    }

    sort (sum+1,sum+M+1, Cmp);
    q=M-R;
    sumafinala=0;
    for (j=1;j<=q;j++)
    {
        i=sum[j].y;
        for (z=1;z<=k;z++)
            sumafinala+=b[i][z];
    }
    summax=max(summax,sumafinala);
}

void Back2(int top,int k)
{
    int i,j;
    /// facem back pe coloane
    /// combinari de n luate cate k unde k=N-C
    if (top==k+1) Afisare2();
    else
        for (i=st[top-1]+1;i<=N-k+top;i++)
    {
        st[top]=i;
        Back2(top+1,k);
    }
}


int main ()
{
   int i,j;
   Citire();
   if (M<=N)
   {
       k=M-R;
       Back1(1,k);
       fout<<summax<<"\n";
   }
   else
   {
       k=N-C;
       Back2(1,k);
       fout<<summax<<"\n";
   }
   fin.close();
   fout.close();
   return 0;
}