Cod sursa(job #169330)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 1 aprilie 2008 16:58:26
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>  
#include <algorithm>  
using namespace std;  
  
long x[600][600], sum[600], maxim, suma, i, j, n, m, r, c, st[600], aux;  
  
void back2(long k, long nr_1)  
{  
    if (k > n + 1) return;  
    if (nr_1 == r)  
    {  
        for (j = 1; j <= m; j++)  
        {  
            sum[j] = 0;  
            for (i = 1; i <= n; i ++)  
                if (!st[i])  
                    sum[j] += x[i][j];  
        }
        sort(sum + 1, sum + m + 1);  
  
        suma = 0;  
        for (i = c + 1; i <= m; i ++)  
            suma += sum[i];  
  
        maxim = suma > maxim ? suma : maxim;  
    }  
    else  
    {  
        st[k] = 1;  
        back2(k + 1, nr_1 + 1);  
        st[k] = 0;  
        back2(k + 1, nr_1);  
    }  
}  
  
void back(long k, long nr_1)  
{  
    if (k > m) return;  
    if (nr_1 == c)  
    {  
        for (i = 1; i <= n; i ++)  
        {  
            sum[i] = 0;  
            for (j = 1; j <= m; j ++)  
                if (!st[j])  
                    sum[i] += x[i][j];  
        }  
        sort(sum + 1, sum + n + 1);  
  
        suma = 0;  
        for (i = r + 1; i <= n; i ++)  
            suma += sum[i];  
  
        maxim = suma > maxim ? suma : maxim;  
    }  
    else  
    {  
        st[k] = 1;  
        back(k + 1, nr_1 + 1);  
        st[k] = 0;  
        back(k + 1, nr_1);  
    }  
}  
  
int main()  
{  
    freopen ("elimin.in", "rt", stdin);  
    freopen ("elimin.out", "wt", stdout);  
  
    scanf("%ld %ld %ld %ld", &n, &m, &r, &c);  
  
    for (i = 1; i <= n; i ++)  
        for (j = 1; j <= m; j ++)  
            scanf("%ld", &x[i][j]);  
  
    if (m <= n)  
        back(1, 0);  
    else  
        back2(1, 0);  
  
    printf("%ld\n", maxim);  
    return 0;  
}