Cod sursa(job #1011662)

Utilizator cdascaluDascalu Cristian cdascalu Data 17 octombrie 2013 09:18:59
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 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];

bitset<Nmax> viz;
void swap_them(int&a, int&b)
{
    int aux = a;a=b;b=aux;
}
void read()
{
    ifstream f("elimin.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_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 max_back = (1<<N),current_s,cnt=0;

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

        if(cnt != R)
            continue;
        current_s = 0;

        copy(sum+1, sum+M+1,aux+1);

        for(int j=1;(1<<(j-1))<=i;++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("elimin.out");
    g<<max_s<<"\n";
    g.close();
    return 0;
}