Pagini recente » Cod sursa (job #1527295) | Cod sursa (job #2923917) | Cod sursa (job #2088490) | Cod sursa (job #616939) | Cod sursa (job #1021458)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int compare(const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
class Matrice
{
int **M, **M_duplicate;
int n, m, r, c;
int *viz;
int *sol;
int *sume;
int s_max;
public:
Matrice()
{
s_max = 0;
}
void Read()
{
ifstream f("elimin.in");
f >> m >> n >> r >> c;
if (m <= n)
{
M = new int*[m];
for (int i = 0; i < m; i++)
M[i] = new int[n];
M_duplicate = new int*[m];
for (int i = 0; i < m; i++)
M_duplicate[i] = new int[n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
f >> M[i][j];
}
else
{
M = new int*[n];
for (int i = 0; i < n; i++)
M[i] = new int[m];
M_duplicate = new int*[n];
for (int i = 0; i < n; i++)
M_duplicate[i] = new int[m];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
f >> M[j][i];
swap(n, m);
swap(r, c);
}
sume = new int[n + 1];
viz = new int[m + 1];
sol = new int[m + 1];
for (int i = 0; i < m; i++)
viz[i] = 0;
f.close();
back(0);
}
void back(int k)
{
if (k == r)
{
Verificare();
return;
}
else
for (int i = 0; i < m;i++)
{
if (k == 0)
{
viz[i] = 1;
sol[k] = i;
back(k + 1);
viz[i] = 0;
}
else
if (!viz[i] && sol[k - 1] < i)
{
viz[i] = 1;
sol[k] = i;
back(k + 1);
viz[i] = 0;
}
}
}
void Verificare()
{
for (int i = 0; i < n; i++)
sume[i] = 0;
for (int i = 0; i < m;i++)
for (int j = 0; j < n; j++)
M_duplicate[i][j] = M[i][j];
int s=0;
for (int i = 0; i < r; i++)
{
for (int j = 0; j < n; j++)
M_duplicate[sol[i]][j] = 0;
}
for (int i = 0; i < n;i++)
for (int j = 0; j < m; j++)
sume[i] += M_duplicate[j][i];
qsort(sume, n, sizeof(int), compare);
for (int i = n-1; i >= c; i--)
s+= sume[i];
if (s>s_max)
s_max = s;
}
void Afisare()
{
ofstream g("elimin.out");
g << s_max;
g.close();
}
};
int main()
{
Matrice M;
M.Read();
M.Afisare();
return 0;
}