Cod sursa(job #35156)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 21 martie 2007 21:06:23
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include<fstream>
#include<stdlib.h>
#include<math.h>
using namespace std;
fstream fin,fout;
int M,N,R,C,a[7300],L[7300],RR,CC,i;
long smax,vec[7300];

void selectez(int p, int q, int &m){
	int i,j,di,dj;
	long aux;
	i=p;j=q;di=+1;dj=0;
	while (i<j){
		if (vec[i]<vec[j]){
			aux=vec[i];vec[i]=vec[j];vec[j]=aux;
			di=1-di;
			dj=1-dj;
			}
		i=i+di;
		j=j-dj;
	}
m=i;
}


void sortez(int p,int q){
	int m;
	if (p<q){
		selectez(p,q,m);
		sortez(p,m-1);
		sortez(m+1,q);
	}
}
		
			
void subm(int k){
	int i,l,j;
	long s;
	if (k>RR){
		for (j=0;j<N;j++){
			s=0;
			for (l=1;l<=RR;l++){
				s=s+a[L[l]*N+j];
			}
			vec[j]=s;
		}
		sortez(0,N-1);
		s=0;
		for (j=0;j<CC;j++)s=s+vec[j];
		if (s>smax)smax=s;
	}
	else
		for (i=L[k-1]+1;i<M-RR+k;i++){
			L[k]=i;
			subm(k+1);
		}
}
		
void subm2(int k){
	int i,l,j;
	long s;
	if (k>CC){
		for (j=0;j<M;j++){
			s=0;
			for (l=1;l<=CC;l++){
				s=s+a[j*N+L[l]];
			}
			vec[j]=s;
		}
		sortez(0,M-1);
		s=0;
		for (j=0;j<RR;j++)s=s+vec[j];
		if (s>smax)smax=s;
	}
	else
		for (i=L[k-1]+1;i<N-CC+k;i++){
			L[k]=i;
			subm2(k+1);
		}
}


int main(void)
{
fin.open("elimin.in",ios::in);
fout.open("elimin.out",ios::out);
fin>>M>>N>>R>>C;
RR=M-R;
CC=N-C;
for (i=0;i<M*N;i++) fin>>a[i];
smax=0;
if (RR<CC)
{
L[0]=-1;
subm(1);
}
else
{
L[0]=-1;
subm2(1);
}
fout<<smax<<endl;
fin.close();
fout.close();
return 0;
}