Pagini recente » Cod sursa (job #348839) | Cod sursa (job #866445) | Cod sursa (job #784887) | Cod sursa (job #123750) | Cod sursa (job #9085)
Cod sursa(job #9085)
#include <stdio.h>
int m,n,r,c,v[15][4000],s[15],nr,smax,sum[4000];
void qSort(int st,int dr)
{
int i=st, j=dr, m=sum[(i+j)/2];
do
{
while (sum[i]<m) i++;
while (sum[j]>m) j--;
if (i<=j)
{
int aux=sum[i]; sum[i]=sum[j]; sum[j]=aux;
i++; j--;
}
}
while (i<=j);
if (st<j) qSort(st,j);
if (i<dr) qSort(i,dr);
}
void sol()
{
for (int i=0;i<n;i++)
{
sum[i]=0;
for (int j=0;j<m;j++)
if (s[j]==1) sum[i]+=v[j][i];
}
qSort(0,n-1);
int aux=0;
for (int i=c;i<n;i++) aux+=sum[i];
if (aux>smax) smax=aux;
}
void back(int k)
{
if (nr==r) sol();
else if (k<m)
for (int i=0;i<2;i++)
{
s[k]=i;
nr+=i;
back(k+1);
nr-=i;
s[k]=0;
}
}
int main()
{
freopen("elimin.in","r",stdin);
scanf("%d %d %d %d",&m,&n,&r,&c);
if (m<=n)
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
scanf("%d",&v[i][j]);
else {
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
scanf("%d",&v[j][i]);
int aux=m; m=n; n=aux;
aux=r; r=c; c=aux;
}
r=m-r;
smax=-1;
nr=0;
back(0);
freopen("elimin.out","w",stdout);
printf("%d\n",smax);
fclose(stdout);
return 0;
}