Cod sursa(job #1011655)

Utilizator cdascaluDascalu Cristian cdascalu Data 17 octombrie 2013 08:57:02
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <bitset>
#define Nmax 7295
#define INF 0x3f3f3f
using namespace std;

int a[Nmax][Nmax],N,M,R,C,max_s = -INF,sum[Nmax],aux[Nmax];

vector<int> col;
bitset<Nmax> viz;
void swap_them(int&a, int&b)
{
    int aux = a;a=b;b=aux;
}
void read()
{
    ifstream f("elim.in");
    f>>N>>M>>R>>C;
    bool swap = false;
    if(N>M)
        swap = true;

    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
            if(swap)
                f>>a[j][i];
            else
                f>>a[i][j];
        }
    if(N>M)
    {
        swap = true;
        swap_them(N,M);
        swap_them(R,C);
    }

}
int main()
{
    read();
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
            sum[j] += a[i][j];

    int min_back = (1<<R) -1, max_back = (1<<(R+1)),current_s;

    for(int i=0;i<max_back;++i)
    {
        viz.reset();
        for(int j=0;j<R+1;++j)
            if((1<<j) & i)
                viz[j+1] = true;

        if(viz.count() != R)
            continue;
        current_s = 0;
        for(int k=1;k<=M;++k)
            aux[k] = sum[k];

        for(int j=1;j<=R+1;++j)
            if(viz[j])
            {
                for(int k=1;k<=M;++k)
                    aux[k] -= a[j][k];
            }
        sort(aux+1, aux+M+1);
        for(int k=M;k>=C;--k)
            current_s += aux[k];
        if(current_s > max_s)
            max_s = current_s;
    }
    ofstream g("elim.out");
    g<<max_s<<"\n";
    g.close();
    return 0;
}