Cod sursa(job #354499)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 8 octombrie 2009 14:47:08
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
#define Nmax 530
using namespace std;

int a[Nmax][Nmax],aux[Nmax][Nmax];
int i,j,n,m,r,c,maxx,y;
int sol[Nmax], sl[Nmax];
int mark[20];

void check(){
	int i,j,sum=0;
   memset(mark,0,sizeof(mark));
   memset(sl,0,sizeof(sl));

   for(i=1;i<=c;++i) mark[sol[i]]=1;
   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j)
       if(!mark[j]) sl[i] +=a[i][j];

   sort(sl+1,sl+n+1);
   for(i=r+1;i<=n;++i) sum+=sl[i];
   if(sum > maxx) maxx=sum;
}

void back(int k){
	int i;
   if(k>c) check(); else
   for(i=sol[k-1]+1;i<=m;++i){
   	sol[k]=i;
      back(k+1);
   }
}

int main(){
	freopen("elimin.in","r",stdin);
   freopen("elimin.out","w",stdout);
   scanf("%d%d%d%d",&n,&m,&r,&c);
   for(i=1;i<=n;++i)
     for(j=1;j<=m;++j) scanf("%d",&a[i][j]);

   if(n<m){ // rotesc matricea
   	for(i=1;i<=n;++i)
        for(j=1;j<=m;++j) aux[i][j]=a[i][j];
      for(j=1;j<=m;++j)
        for(i=n;i>=1;--i) a[j][n-i+1]=aux[i][j];
      y=m; m=n; n=y;
      y=r; r=c; c=y;
   }

   back(1);

   printf("%d\n",maxx);
   fclose(stdin); fclose(stdout);
   return 0;
}