Pagini recente » Cod sursa (job #202444) | Cod sursa (job #693784) | Monitorul de evaluare | Istoria paginii runda/test4234234 | Cod sursa (job #189056)
Cod sursa(job #189056)
#include <stdio.h>
#include <algorithm>
#define Nmax 222
#define N 20
using namespace std;
long long bestS,Suma;
int v[Nmax];
int m,n,c,r;
int a[Nmax][Nmax],b[Nmax][Nmax];
int sol[N];
int rot(int mb[Nmax][Nmax],int ma[Nmax][Nmax])
{
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)
ma[j][m+1-i]=mb[i][j];
return 0;
}
void roteste()
{
int aux;
rot(a,b);
for(int i=0;i<=n;++i)
for(int j=0;j<=m+1;++j)
a[i][j]=b[i][j];
for(int i=1;i<=n;++i)
a[i][0]=a[i][m+1];
aux=r; r=c; c=aux;
aux=m; m=n; n=aux;
}
void print()
{
long long Si=Suma;
for(int i=1;i<=m;++i)
v[i]=a[i][0];
for(int i=1;i<=c;++i)
{
Si-=a[0][sol[i]];
for(int j=1;j<=m;++j)
v[j]-=a[j][sol[i]];
}
sort(v+1,v+m+1);
//for(int i=1;i<=m;++i)
// printf("%d ",v[i]);
//printf(" S=%d ",Si);
//for(int j=1;j<=c;++j)
// printf("%d ",sol[j]);
// printf(" : ");
for(int i=1;i<=r;++i)
{
Si-=v[i];
//printf("%d ",v[i]);
}
//printf("\n");
if(Si>bestS)
{
bestS=Si;
//for(int i=1;i<=c;++i)
// printf("%d ",sol[i]);
//printf("\n");
}
}
void back(int x)
{
if(x==c)
print();
else
for(int i=sol[x]+1;i<=n;++i)
{
sol[x+1]=i;
back(x+1);
}
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d%d%d%d", &m,&n,&r,&c);
for(int i=1;i<=m;++i)
for(int j=1;j<=n;++j)
{
scanf("%d", &a[i][j]);
Suma+=a[i][j];
a[i][0]+=a[i][j];
a[0][j]+=a[i][j];
}
if(m<n)
roteste();
/*for(int i=0;i<=m;++i)
for(int j=0;j<=n+2;++j)
{
printf("%d ",a[i][j]);
if(j==n+2)
printf("\n");
}*/
back(0);
printf("%lld\n",bestS);
return 0;
}