Cod sursa(job #91751)

Utilizator tm_raduToma Radu tm_radu Data 13 octombrie 2007 13:58:41
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <stdio.h>

int n, m;
int r, c;
int a[16][600];
int s[601], sum;
int i, j, k, l;
int x[16];
int nr1;
int smax;

void Back(int k);
void Qsort(int st, int dr);
void Solve();

int main()
{
    freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);
    scanf("%d %d %d %d", &m, &n, &r, &c);
    if ( m <= n )
    {
        for ( i = 1; i <= m; i++ )
            for ( j = 1; j <= n; j++ )
                scanf("%d", &a[i][j]);
    }
    else
    {
        m = m+n; n = m - n; m = m - n;
        r = r+c; c = r - c; r = r - c;
        for ( i = 1; i <= n; i++ )
            for ( j = 1; j <= m; j++ )
                scanf("%d", &a[j][i]);    
    }
    Back(1);     
    printf("%d\n", smax);
    return 0; 
}

void Back(int k)
{
    for ( int i = 0; i <= 1; i++ )
    {
        x[k] = i;
        nr1 += i;
        if ( k == m )          
        {
            if ( nr1 == m-r ) Solve();
        }
        else Back(k+1);
        nr1 -= i;
    }
}

void Qsort(int st, int dr)
{
    int i = st-1;
    int j = dr+1;
    int mij = st;
    do
    {
        do { i++; } while ( s[i] > s[mij] );
        do { j--; } while ( s[j] < s[mij] );
        if ( i <= j )
        {
            int aux = s[i];
            s[i] = s[j];
            s[j] = aux;
        }
    } while ( i <= j );
    if ( i < dr ) Qsort(i, dr);
    if ( st < j ) Qsort(st, j);
}

void Solve()
{
    for ( j = 1; j <= n; j++ )
    {
        s[j] = 0;
        for ( i = 1; i <= m; i++ )
            if ( x[i] ) 
                s[j] += a[i][j];
    }    
    Qsort(1, n);
    sum = 0;
    for ( i = 1; i <= n-c; i++ )
        sum += s[i];
    if ( sum > smax ) smax = sum;
}