Cod sursa(job #1749878)

Utilizator dragomirmanuelDragomir Manuel dragomirmanuel Data 29 august 2016 00:51:01
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int M,N,R,C;

int a[80][7250],sol[7250];
int SC[7250];

void Read()
{
    scanf("%d%d%d%d",&M,&N,&R,&C);

    if(M>N)
    {
    for(int j=1;j<=M;j++)
        for(int i=1;i<=N;i++)
        scanf("%d", &a[i][j]);
    swap(M,N);
    swap(R,C);
    }

    else
    {
        for(int i=1;i<=M;i++)
            for(int j=1;j<=N;j++)
            scanf("%d", &a[i][j]);
    }

}

void Reset()
{
    for(int i=1;i<=N;i++)
        SC[i]=0;
}

int maxi=-1;

void Solve()
{
    Reset();
    int stotal=0;

    for(int j=1;j<=N;j++)
      { for(int i=1;i<=(M-R);i++)
            SC[j]+=a[sol[i]][j];
        stotal+=SC[j];
      }

    sort(SC+1,SC+N+1);


    for(int j=1;j<=C;j++)
        stotal-=SC[j];

    if(maxi<stotal) maxi=stotal;

}

void BK(int k)
{
    if(k==M-R+1)
    {
        Solve();
        return;
    }

    for(int v=sol[k-1]+1; v<=M-(M-R)+k; ++v)
    {
        sol[k]=v;
        BK(k+1);
    }
}

void Write()
{
     for(int i=1;i<=M;i++)
            { for(int j=1;j<=N;j++)
                cout<<a[i][j]<<" ";
            cout<<"\n";}
}

int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);

    Read();
    BK(1);
    printf("%d",maxi);

    return 0;
}