Pagini recente » Cod sursa (job #2207186) | Cod sursa (job #2722278) | Cod sursa (job #3140092) | Cod sursa (job #308476) | Cod sursa (job #2417082)
#include <bits/stdc++.h>
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");
const int DIM = 8000;
int v[DIM][DIM];
int t[DIM][DIM];
int p[DIM];
int ps[DIM];
int best = 0;
int sum = 0;
int n, m;
bitset <DIM> vis;
void rotate()
{
for(int i = m; i >= 1; i--)
for(int j = 1; j <= n; j++)
t[m - i + 1][j] = v[j][i];
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
v[i][j] = t[i][j];
}
bool cmp(int a, int b)
{
if(ps[a] <= ps[b])
return true;
return false;
}
int r, c;
void back(int r, int c, int last)
{
if(r == 0)
{
sort(p + 1, p + 1 + m, cmp);
int s = 0;
for(int j = c + 1; j <= m; j++)
s += ps[p[j]];
best = max(best, s);
}
else
{
for(int i = last + 1; i <= n && n - i >= r - 1; i++)
if(vis[i] == 0)
{
vis[i] = 1;
for(int j = 1; j <= m; j++)
ps[j] -= v[i][j];
back(r - 1, c, i);
for(int j = 1; j <= m; j++)
ps[j] += v[i][j];
vis[i] = 0;
}
}
}
main()
{
in >> n >> m >> r >> c;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
in >> v[i][j];
sum += v[i][j];
}
if(n > m)
{
rotate();
swap(n, m);
swap(r, c);
}
for(int i = 1; i <= m; i++)
p[i] = i;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
ps[j] += v[i][j];
back(r, c, 0);
out << best;
}