Cod sursa(job #7121)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 21 ianuarie 2007 12:37:15
Problema Elimin Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasa a 10-a Marime 1.28 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int A[8000],S[8000],R[8000],n,m,a,b,mx;

void WriteData()
{
 freopen("elimin.out","w",stdout);
 printf("%d\n",mx);
 fclose(stdout);
}

void ReadData()
{
 int i,j;
 freopen("elimin.in","r",stdin);
 scanf("%d %d %d %d", &n, &m, &a, &b);
 for (i=0;i<n;i++)
    for (j=0;j<m;j++)
       scanf("%d", &A[i*m+j]);
 fclose(stdin);
}

void Gata1()
{
 int i,j,sum;
 memset(R,0,(m+1)*sizeof(int));
 for (i=0;i<n;i++)
    if (!S[i])
    for (j=0;j<m;j++) R[j]+=A[i*m+j];
 sort(R,R+m);sum=0;
 for (i=b;i<m;i++) sum+=R[i];
 if (sum>mx) mx=sum;
}

void Gata2()
{
 int i,j,sum;
 memset(R,0,(n+1)*sizeof(int));
 for (i=0;i<m;i++)
    if (!S[i])
    for (j=0;j<n;j++) R[j]+=A[j*m+i];
 sort(R,R+n);sum=0;
 for (i=a;i<n;i++) sum+=R[i];
 if (sum>mx) mx=sum;
}

void Back1(int x, int y)
{
 int i;
 if (x)
   for (i=y;i<=n-x;i++) {
       S[i]=1;
       Back1(x-1,y+1);
       S[i]=0;
    } else Gata1();
}

void Back2(int x, int y)
{
 int i;
 if (x)
   for (i=y;i<=m-x;i++) {
       S[i]=1;
       Back2(x-1,y+1);
       S[i]=0;
    } else
   Gata2();
}

void Solve() { if (n-a>m-b) Back2(b,0); else Back1(a,0); }

int main()
{
 ReadData();
 Solve();
 WriteData();
}