Cod sursa(job #1013909)

Utilizator maritimCristian Lambru maritim Data 21 octombrie 2013 21:42:16
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

#define MaxN 20
#define MaxM 7100

int N,M,R,C,Sol;
int A[MaxN][MaxM];
int V[MaxN],viz[MaxN],B[MaxM];

void citire(void)
{
    f >> N >> M >> R >> C;

    if(N > M)
    {
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                f >> A[j][i];

        int aux = N; N = M; M = aux;
        aux = R; R = C; C = aux;
    }
    else
    {
        for(int i=1;i<=N;i++)
            for(int j=1;j<=M;j++)
                f >> A[i][j];
    }
}

inline int newSol(void)
{
    int Sol = 0;

    for(int i=1;i<=M;i++)
        B[i] = 0;

    for(int i=1;i<=N;i++)
        if(!viz[i])
            for(int j=1;j<=M;j++)
                B[j] += A[i][j];

    sort(B+1,B+M+1);

    for(int i=C+1;i<=M;i++)
        Sol += B[i];

    return Sol;
}

inline void back(int k)
{
    if(k == R+1)
    {
        Sol = max(Sol,newSol());

        return ;
    }

    for(int i=V[k-1]+1;i<=N;i++)
    {
        V[k] = i;
        viz[i] = 1;
        back(k+1);
        viz[i] = 0;
    }
}

int main()
{
    citire();

/*    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
            cout << A[i][j] << " ";
            cout << "\n";
    }*/
    back(1);
    
    g << Sol << "\n";
}