Pagini recente » Cod sursa (job #753808) | Cod sursa (job #1037533) | Cod sursa (job #625650) | Cod sursa (job #3282428) | Cod sursa (job #120620)
Cod sursa(job #120620)
#include <stdio.h>
#include <algorithm>
using namespace std;
long x[600][600], sum[600], maxim, suma, i, j, n, m, r, c, st[600], aux;
void back2(long k, long nr_1)
{
if (k > n + 1) return;
if (nr_1 == r)
{
for (int j = 1; j <= m; j ++)
{
sum[j] = 0;
for (int i = 1; i <= n; i ++)
if (!st[i])
sum[j] += x[i][j];
}
sort(sum + 1, sum + m + 1);
suma = 0;
for (int i = c + 1; i <= m; i ++)
suma += sum[i];
maxim = suma > maxim ? suma : maxim;
}
else
{
st[k] = 1;
back2(k + 1, nr_1 + 1);
st[k] = 0;
back2(k + 1, nr_1);
}
}
void back(long k, long nr_1)
{
if (k > m) return;
if (nr_1 == c)
{
for (int i = 1; i <= n; i ++)
{
sum[i] = 0;
for (int j = 1; j <= m; j ++)
if (!st[j])
sum[i] += x[i][j];
}
sort(sum + 1, sum + n + 1);
suma = 0;
for (int i = r + 1; i <= n; i ++)
suma += sum[i];
maxim = suma > maxim ? suma : maxim;
}
else
{
st[k] = 1;
back(k + 1, nr_1 + 1);
st[k] = 0;
back(k + 1, nr_1);
}
}
int main()
{
freopen ("elimin.in", "rt", stdin);
freopen ("elimin.out", "wt", stdout);
scanf("%ld %ld %ld %ld", &n, &m, &r, &c);
for (i = 1; i <= n; i ++)
for (j = 1; j <= m; j ++)
scanf("%ld", &x[i][j]);
if (m <= n)
back(1, 0);
else
back2(1, 0);
printf("%ld\n", maxim);
return 0;
}