Pagini recente » Cod sursa (job #276906) | Cod sursa (job #1697572) | Cod sursa (job #1882003) | Cod sursa (job #326980) | Cod sursa (job #1098166)
#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 7300
using namespace std;
int ok,n,m,R,C,sol=-1;
int x[maxn],s[maxn];
vector<int> a[maxn];
void read()
{
int x;
scanf("%d%d%d%d",&n,&m,&R,&C);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&x),a[i].pb(x);
}
int detR()
{
int Cval,sum=0,c;
for(int i=1;i<=m;i++)
{
s[i]=0;
for(int j=1;j<=n;j++)
if(x[j]) s[i]+=a[j][i-1];
sum+=s[i];
}
nth_element(s+1,s+C,s+m+1); Cval=s[C]; c=C;
for(int i=1;i<=m;i++) if(s[i]<Cval) sum-=s[i],c--;
sum-=(Cval*c);
return sum;
}
int detC()
{
int Rval,sum=0,r;
for(int i=1;i<=n;i++)
{
s[i]=0;
for(unsigned int j=0;j<a[i].size();j++)
if(x[j+1]) s[i]+=a[i][j];
sum+=s[i];
}
nth_element(s+1,s+R,s+n+1); Rval=s[R]; r=R;
for(int i=1;i<=n;i++) if(s[i]<Rval) sum-=s[i],r--;
sum-=(Rval*r);
return sum;
}
void backR(int k,int nr)
{
if(k>n && nr==R){sol=max(sol,detR()); return;}
if(k>n) return;
x[k]=1; backR(k+1,nr);
if(nr==R) return;
x[k]=0; backR(k+1,nr+1);
}
void backC(int k,int nr)
{
if(k>m && nr==C){sol=max(sol,detC()); return;}
if(k>m) return;
x[k]=1; backC(k+1,nr);
if(nr==C) return;
x[k]=0; backC(k+1,nr+1);
}
void solve()
{
if(n<=m) backR(1,0);
else backC(1,0);
}
int main()
{
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
read();
solve();
printf("%d",sol);
fclose(stdin);
fclose(stdout);
return 0;
}