Pagini recente » Cod sursa (job #1293086) | Cod sursa (job #2641284) | Cod sursa (job #1692942) | Cod sursa (job #3144029) | Cod sursa (job #7112)
Cod sursa(job #7112)
#include <stdio.h>
#define NMAX 550
typedef struct stiva
{
int nr, val;
};
long lin[NMAX], col[NMAX];
long a[NMAX][NMAX];
long n, m, r, c;
long suma, h2;
long min = 2000000000;
long uzc[NMAX], uzl[NMAX], h = 0, plus, sol;
long flinie[NMAX];
long fcoloana[NMAX];
void read()
{
long i, j, x;
scanf("%ld %ld %ld %ld\n", &n, &m, &r, &c);
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= m; ++j)
{
scanf("%ld ", &a[i][j]);
lin[i] += a[i][j];
col[j] += a[i][j];
suma += a[i][j];
}
scanf("\n");
}
}
void back(long linii, long coloane)
{
long i, for1, for2, j;
if(linii == r && coloane == c)
{
for(for1 = plus = 0; for1 < h; ++for1)
for(for2 = 0; for2 < h2; ++for2)
plus += a[uzl[for1]][uzc[for2]];
if(min > sol-plus)
min = sol-plus;
}
else
{
for(i = 1; i <= n; ++i)
{
if(linii < r && !flinie[i])
{
sol += lin[i];
uzl[h++] = i;
flinie[i] = 1;
back(linii+1, coloane);
--h;
sol -= lin[i];
flinie[i] = 0;
}
}
for(j = 1; j <= m; ++j)
{
if(coloane < c && !fcoloana[j])
{
sol += col[j];
uzc[h2++] = j;
fcoloana[j] = 1;
back(linii, coloane+1);
sol -= col[j];
fcoloana[j] = 0;
--h2;
}
}
}
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
read();
back(0, 0);
printf("%ld\n", suma-min);
fclose(stdin);
fclose(stdout);
return 0;
}