Pagini recente » Cod sursa (job #2024808) | Cod sursa (job #2017899) | Profil M@2Te4i | Cod sursa (job #484525) | Cod sursa (job #1260880)
#include <algorithm>
#include <fstream>
using namespace std;
ifstream in( "elimin.in" );
ofstream out( "elimin.out" );
const int NMAX= 20, MMAX= 8000, inf= 1<<30;
int A[NMAX+1][MMAX+1];
int N, M, l, c, sol=-inf;
int s[MMAX+1], u[NMAX+1];
void backtrack( int x, int last )
{
if ( x==l+1 )
{
for ( int i= 1; i<=N; ++i )
{
for ( int j= 1; j<=M; ++j )
{
s[j]+= A[i][j]*( (u[i]+1)%2 );
}
}
sort( s+1, s+M+1 );
int sum= 0;
for ( int i= M; i>c; --i )
{
sum+= s[i];
}
if ( sum>sol )
{
sol= sum;
}
for ( int i= 1; i<=M; ++i )
{
s[i]= 0;
}
}
else
{
for ( int i= last+1; i<=N; ++i )
{
u[i]= 1;
backtrack(x+1, i);
u[i]= 0;
}
}
}
int main( )
{
in >> N >> M >> l >> c;
if ( N>NMAX )
{
for ( int i= 1; i<=N; ++i )
{
for ( int j= 1; j<=M; ++j )
{
in >> A[j][i];
}
}
swap(N, M), swap(l, c);
}
for ( int i= 1; i<=N; ++i )
{
for ( int j= 1; j<=M; ++j )
{
in >> A[i][j];
}
}
backtrack(1,0);
out << sol << '\n';
return 0;
}