Cod sursa(job #1083562)

Utilizator leontinLeontin leontin Data 16 ianuarie 2014 03:59:20
Problema Elimin Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.19 kb
#include<fstream>
#include <algorithm>

using namespace std;

#define max 600
#define min 30

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

int n, m, r, c;
short a[max][min];

int erasee[max] = {0};

int s = 0;

void read()
{
  f>>m>>n>>r>>c;

    if ( m <= n )
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 0; j < n; ++j )
              f>>a[n-j][i];

        n = n ^ m;
        m = n ^ m;
        n = n ^ m;

        r = r ^ c;
        c = r ^ c;
        r = r ^ c;

    }
    else
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
               f>>a[i][j];

    }
}

void suma()
{
    int t = 0;
    int b[max] = {0};

    for ( int i = 1; i <= m; ++i )
    {
        for ( int j = 1; j <= n; ++j )
        {
            if ( !erasee[j] )
                b[i] += a[i][j];
        }
    }

    sort(b+1, b+m+1);

    for ( int i = r+1; i <= m; ++i )
        t += b[i];

    if ( t > s )
        s = t;

    for ( int i = 1; i <= n; ++i )
        erasee[i] = 0;
}

short st[max] = {0};

void back(int col)
{
    for ( int i = st[col-1]+1; i <= n; ++i )
    {
        st[col] = i;

        if ( col == c )
        {
            for ( int t = 1; t <= c; ++t )
                erasee[st[t]] = 1;

            suma();
        }
        else
        {
            back(col+1);
        }
    }
}

int main()
{
    read();


    if ( c == 0 && r == 0 )
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
                s += a[i][j];
    }
    else if ( c == 0 )
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
                erasee[i] += a[i][j];

        sort(erasee+1, erasee+m+1);
        for ( int i = r+1; i <= m; ++i )
            s += erasee[i];
    }
    else if ( r == 0 )
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
                erasee[j] += a[j][i];

        sort(erasee+1, erasee+n+1);
        for ( int i = c+1; i <= n; ++i )
            s += erasee[i];
    }
    else
        back(1);
 g<<s;

    return 0;
}