Pagini recente » Cod sursa (job #1826007) | Cod sursa (job #2250754) | Cod sursa (job #481428) | Cod sursa (job #2112771) | Cod sursa (job #91751)
Cod sursa(job #91751)
#include <stdio.h>
int n, m;
int r, c;
int a[16][600];
int s[601], sum;
int i, j, k, l;
int x[16];
int nr1;
int smax;
void Back(int k);
void Qsort(int st, int dr);
void Solve();
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
scanf("%d %d %d %d", &m, &n, &r, &c);
if ( m <= n )
{
for ( i = 1; i <= m; i++ )
for ( j = 1; j <= n; j++ )
scanf("%d", &a[i][j]);
}
else
{
m = m+n; n = m - n; m = m - n;
r = r+c; c = r - c; r = r - c;
for ( i = 1; i <= n; i++ )
for ( j = 1; j <= m; j++ )
scanf("%d", &a[j][i]);
}
Back(1);
printf("%d\n", smax);
return 0;
}
void Back(int k)
{
for ( int i = 0; i <= 1; i++ )
{
x[k] = i;
nr1 += i;
if ( k == m )
{
if ( nr1 == m-r ) Solve();
}
else Back(k+1);
nr1 -= i;
}
}
void Qsort(int st, int dr)
{
int i = st-1;
int j = dr+1;
int mij = st;
do
{
do { i++; } while ( s[i] > s[mij] );
do { j--; } while ( s[j] < s[mij] );
if ( i <= j )
{
int aux = s[i];
s[i] = s[j];
s[j] = aux;
}
} while ( i <= j );
if ( i < dr ) Qsort(i, dr);
if ( st < j ) Qsort(st, j);
}
void Solve()
{
for ( j = 1; j <= n; j++ )
{
s[j] = 0;
for ( i = 1; i <= m; i++ )
if ( x[i] )
s[j] += a[i][j];
}
Qsort(1, n);
sum = 0;
for ( i = 1; i <= n-c; i++ )
sum += s[i];
if ( sum > smax ) smax = sum;
}