Pagini recente » Borderou de evaluare (job #1551171) | Cod sursa (job #2541899)
//#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("elimin.in");
ofstream cout("elimin.out");
int mn(int a,int b){
if(a<b)
return a;
return b;
}
int vect[8000],summ=0;
int put[30],n,m,f[8000],v[8000][8000],a,b,minim=999999,sn[8000],sm[8000];
int ve[8000];
void bctn(){
for(int i=0;i<put[n];i++){
int stare=i,cnt=0;
for(int j=1;j<=n;j++)
f[j]=0;
for(int j=1;j<=m;j++)
vect[j]=0;
long long suma=0,contor=0;
for(int j=1;j<=n;j++){
if(stare%2==1){
ve[++contor]=j;
}
stare/=2;
}
if(contor!=a)
continue;
for(int j=1;j<=a;j++){
for(int k=1;k<=m;k++)
suma+=v[ve[j]][k];
}
for(int j=1;j<=m;j++){
vect[j]=sm[j];
}
for(int j=1;j<=a;j++){
for(int k=1;k<=m;k++){
vect[k]-=v[ve[j]][k];
}
}
/*for(int k=1;k<=m;k++){
int sum=0;
for(int j=1;j<=n;j++){
if(f[j]==0){
sum+=v[j][k];
}
}
vect[k]=sum;
}
*/
//cout<<suma<<"\n";
sort(vect+1,vect+m+1);
for(int j=1;j<=b;j++){
suma+=vect[j];
}
minim=mn(minim,suma);
//cout<<suma<<"\n";
/**for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
s[i][j]=s[]
}
}
*/
}
cout<<summ-minim;
}
void bctm(){
for(int i=0;i<put[m];i++){
int stare=i,cnt=0;
for(int j=1;j<=m;j++)
f[j]=0;
for(int j=1;j<=n;j++)
vect[j]=0;
long long suma=0,contor=0;
for(int j=1;j<=m;j++){
if(stare%2==1){
ve[++contor]=j;
}
stare/=2;
}
if(contor!=b){
continue;
}
for(int j=1;j<=a;j++){
for(int k=1;k<=n;k++)
suma+=v[k][ve[j]];
}
/*for(int k=1;k<=n;k++){
for(int j=1;j<=m;j++){
if(f[j]==1){
suma+=v[k][j];
}
}
}
*/
/*for(int j=1;j<=m;j++){
if(f[j]==1){
for(int k=1;k<=n;k++){
suma+=v[k][j];
}
}
}
*/
for(int j=1;j<=n;j++){
vect[j]=sn[j];
}
for(int j=1;j<=b;j++){
for(int k=1;k<=n;k++){
vect[k]-=v[k][ve[j]];
}
}
//cout<<suma<<"\n";
sort(vect+1,vect+n+1);
for(int j=1;j<=a;j++){
suma+=vect[j];
}
minim=mn(minim,suma);
//cout<<suma<<"\n";
/**for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
s[i][j]=s[]
}
}
*/
}
cout<<summ-minim;
}
int main()
{
cin>>n>>m>>a>>b;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>v[i][j];
sn[i]+=v[i][j];
sm[j]+=v[i][j];
summ+=v[i][j];
}
}
put[0]=1;
for(int j=1;j<=20;j++){
put[j]=put[j-1]*2;
}
if(n<m){
bctn();
}
else{
bctm();
}
return 0;
}