Pagini recente » Cod sursa (job #3166885) | Cod sursa (job #3215623) | Cod sursa (job #1382663) | Cod sursa (job #3247677) | Cod sursa (job #2740250)
#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] = -1;
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;
}