Pagini recente » Cod sursa (job #2370765) | Cod sursa (job #3143527) | Cod sursa (job #278893) | Cod sursa (job #1091322) | Cod sursa (job #1061225)
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
int n, m, r, c, St;
int **a;
int *sumc, *suml;
int *v;
int smin = 320000000 ;
int greedy(bool linie)
{
vector<int> h;
int i;
if (linie)
{
for (i = 1; i <= m; i++)
h.push_back(sumc[i]);
}
else
{
for (i = 1; i <= n; i++)
h.push_back(suml[i]);
}
sort(h.begin(), h.end());
int s = 0;
if (linie)
{
for (i = 0; i < c; i++)
s += h[i];
return s;
}
else
{
for (i = 0; i < r; i++)
s += h[i];
return s;
}
h.clear();
}
void Back(int k, int nn, bool linie, int sum, int cate)
{
int i;
if(nn == 0) smin = greedy(linie);
else
for (v[k] = v[k - 1] + 1; v[k] <= nn; v[k]++)
{
int s = 0;
if (linie)
{
s = suml[v[k]];
for (i = 1; i <= m; i++)
sumc[i] -= a[v[k]][i];
}
else
{
s = sumc[v[k]];
for (i = 1; i <= n; i++)
suml[i] -= a[i][v[k]];
}
if (k == cate)
{
s += sum;
s += greedy(linie);
if (s < smin)
smin = s;
}
else
Back(k + 1, nn, linie, sum + s, cate);
if (linie)
for (i = 1; i <= m; i++)
sumc[i] += a[v[k]][i];
else
for (i = 1; i <= n; i++)
suml[i] += a[i][v[k]];
}
}
int main()
{
ifstream fin("elimin.in");
ofstream fout("elimin.out");
fin>>n>>m>>r>>c;
a = new int*[n+5];
suml = new int[n+5];
sumc = new int[m+5];
for (int i = 1; i <= n; i++)
{
a[i] = new int[m+5];
for (int j = 1; j <= m; j++)
{
fin>>a[i][j];
St += a[i][j];
suml[i] += a[i][j];
sumc[j] += a[i][j];
}
}
if (n < m)
{
v = new int[n+5];
v[0] = 0;
Back(1, n, true, 0, r);
}
else
{
v = new int[m+5];
v[0] = 0;
Back(1, m, false, 0, c);
}
fout<<St - smin;
}