Cod sursa(job #8879)

Utilizator goguGogu Marian gogu Data 25 ianuarie 2007 22:13:51
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>
#include <string>
#include <algorithm>

using namespace std;

typedef int lin[1024];
int n, m, r, c, best;
int a[15][1024];
lin x;

void back(int lev, int mai, lin sum)
{
    int i,j,k=0;
    lin s;
    memcpy(s, sum, 4*m);
    if (lev==n){
       sort(s, s+m);
       for (i=c; i<m; i++)
           k+=s[i];
       if (k>best) best=k;
       return;   
    }
    if (mai)
       for (i=0, mai--; i<m; i++) s[i]+=a[lev][i];
    for (i=lev+1; i<=n-mai; i++)
        if (mai>0 || i==n) back(i, mai, s);
}

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