Cod sursa(job #872434)

Utilizator MKLOLDragos Ristache MKLOL Data 6 februarie 2013 01:08:09
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#define BUFFER_SIZE 8192
using namespace std;
int v[101];

int N,M,R,C,NR,MA,ok,rez=-12345;
int l[2023];
vector<vector<short> > a;
int w[2023],ret;
char buff[BUFFER_SIZE];
int buffIt;
FILE *inputFile = fopen("elimin.in", "r");

inline int getNumber() {
  int ret = 0;

  while (buff[buffIt] < '0' || buff[buffIt] > '9')
    if (++buffIt == BUFFER_SIZE)
      fread(buff, BUFFER_SIZE, 1, inputFile),
      buffIt = 0;

  while (buff[buffIt] >= '0' && buff[buffIt] <= '9') {
    ret = ret * 10 + buff[buffIt] - '0';

    if (++buffIt == BUFFER_SIZE) {
      buffIt = 0;
      fread(buff, BUFFER_SIZE, 1, inputFile);
    }
  }
  return ret;
}

inline void make()
{
    ret=0;
    for(int i=1;i<=max(N,M);++i)
        l[i]=0;

  //  printf("\n");
    if(ok==1)
    {
        for(int i=1;i<=N;++i)
        {   if(w[i]==0)
            for(int j=1;j<=M;++j)
            {


                l[j]+=a[i][j];
            }
        }
        nth_element(l+1,l+C,l+M+1);
        for(int i=C+1;i<=M;++i)
        {
            ret+=l[i];
        }
    }
    else
    {
        for(int j=1;j<=M;++j)
            {
            if(w[j]==0)
        for(int i=1;i<=N;++i)
        {

                l[i]+=a[i][j];
            }
        }
        nth_element(l+1,l+R,l+N+1);
        for(int i=R+1;i<=N;++i)
        {
            ret+=l[i];
        }

    }

    if(ret>rez)
        rez=ret;
}


void back(int k)
{
    if(k==NR+1)
    {
    make();
    }
    else
    {
        for(int i=v[k-1]+1;i<=MA;++i)
        {

            v[k]=i;
            w[i]=1;
            back(k+1);
            w[i]=0;
        }
    }
}

int main()
{

ofstream fout("elimin.out");
N=getNumber();
M=getNumber();
R=getNumber();
C=getNumber();
     a.resize(N+1);

    for(int i=1;i<N+1;++i)
    {
        a[i].resize(M+1);

    }
    for(int i=0;i<N+3;++i)
    {

    }
    if(N<M)
    {
    ok=1;
    MA=N;
    NR=R;
    }
    else
    {
    ok=2;
    MA=M;
    NR=C;
    }
   // printf("%d %d %d %d",N,M,R,C);
    for(int i=1;i<=N;++i)
        for(int j=1;j<=M;++j)
        {
        a[i][j]=getNumber();
        }

    back(1);
   fout<<rez;
    return 0;
}