Cod sursa(job #60049)

Utilizator DastasIonescu Vlad Dastas Data 11 mai 2007 22:31:41
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.85 kb
#include <cstdio>
#include <iostream>
#define max 550

FILE *in = fopen("elimin.in","r"), *out = fopen("elimin.out","w");

int n, m, r, c;
short a[max][max] = {{0}};
int eliminate[max] = {0};

int s = 0;

void read()
{
    fscanf(in, "%d %d %d %d", &m, &n, &r, &c);


    if ( m <= n )
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
                fscanf(in, "%d" , &a[n-j+1][i]);

        int tt = m;
        m = n;
        n = tt;

        tt = r;
        r = c;
        c = tt;
    }
    else
    {
        for ( int i = 1; i <= m; ++i )
            for ( int j = 1; j <= n; ++j )
                fscanf(in, "%d" , &a[i][j]);

    }
}

int partition(int top, int bottom, int arr[])
{
     int x = arr[top];
     int i = top - 1;
     int j = bottom + 1;
     int temp;
     do
     {
        do
        {
            --j;
        } while ( x < arr[j] );

        do
        {
            ++i;
        } while ( x > arr[i] );

        if ( i < j )
        {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
     } while ( i < j );

     return j;
}

void quicksort(int top, int bottom, int arr[])
{
    int middle;
    if ( top < bottom )
    {
        middle = partition(top, bottom, arr);
        quicksort(top, middle, arr);
        quicksort(middle+1, bottom, arr);
    }

    return;
}

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

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

    quicksort(0, m, b);

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

    if ( t > s )
        s = t;

    memset(eliminate, 0, sizeof(eliminate));

}

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 )
                eliminate[st[t]] = 1;

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

//==================================================================================================

//void rot()
//{
//    int b[max][max] = {{0}};
//
//    for ( int i = 1; i <= n; ++i )
//        for ( int j = 1; j <= m; ++j )
//            b[i][j] = a[j][n-i+1];
//
//    for ( int i = 1; i <= n; ++i )
//        for ( int j = 1; j <= m; ++j )
//            a[i][j] = b[i][j];
//
//}

int main()
{
    read();

//    for ( int i = 1 ; i <= m; ++i )
//    {
//        for ( int j = 1; j <= n; ++j )
//            printf("%d ", a[i][j]);
//        printf("\n");
//    }
//    printf("\n");

//    if ( m < n )
//    {
//        rot();
//        int t = m;
//        m = n;
//        n = t;
//
//        t = r;
//        r = c;
//        c = t;
//    }
//    for ( int i = 1 ; i <= m; ++i )
//    {
//        for ( int j = 1; j <= n; ++j )
//            printf("%d ", a[i][j]);
//        printf("\n");
//    }

    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 )
                eliminate[i] += a[i][j];

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

        quicksort(0, n, eliminate);
        for ( int i = c+1; i <= n; ++i )
            s += eliminate[i];
    }
    else
        back(1);

    fprintf(out, "%d\n", s);

	return 0;
}