Pagini recente » Cod sursa (job #2359705) | Cod sursa (job #2270208) | Cod sursa (job #1533532) | Cod sursa (job #614570) | Cod sursa (job #2740253)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ( "elimin.in" );
ofstream cout ( "elimin.out" );
const int DIV_MAX = 15;
const int NMAX = 7294;
int a[DIV_MAX+1][NMAX+1];
int col[NMAX+1];
int ord[NMAX+1];
int n,m,r,c;
int st[DIV_MAX + 1];
int maxy = 0;
int sum_all(int m)
{
int s=0;
for (int i=1;i<=m;i++ )
s+=col[i];
return s;
}
bool cmp(int a,int b)
{
return col[a]<col[b];
}
void bkt (int k)
{
if (k==r+1)
{
sort(ord+1,ord+m+1,cmp);
int s = sum_all (m);
int smin=0;
for (int i=1;i<=c;i++)
smin+=col[ord[i]];
if(s-smin>maxy)
maxy=s-smin;
return;
}
for (int i=st[k-1]+1;i<=n-r+k;i++)
{
st[k]=i;
for (int j=1;j<=m;j++ )
col[j]-= a[i][j];
bkt(k + 1 );
for (int j=1;j<=m;j++ )
col[j]+= a[i][j];
}
}
int main() {
int i, j, aux;
cin>>n>>m>>r>>c;
if (n<m)
for (i=1;i<=n;i++)
for (j=1;j<=m;j++ )
cin>>a[i][j];
else
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++ )
cin>>a[j][i];
aux=n;
n=m;
m=aux;
aux=r;
r=c;
c=aux;
}
for (i=1;i<=m;i++)
ord[i]=i;
for(i=1;i<=n;i++)
for (j=1;j<=m;j++ )
col[j]+=a[i][j];
st[0]=0;
bkt (1); // nu am facut cu descompunerea in baza 2 deoarece
// trebuia sa verificam pt fiecare indice nr de biti 1
cout << maxy;
return 0;
}