Pagini recente » Cod sursa (job #2483973) | Cod sursa (job #2880863) | Cod sursa (job #1683783) | Cod sursa (job #2179891) | Cod sursa (job #1072634)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string.h>
const static int NMAX = 700;
using namespace std;
int nr_linii , nr_coloane , matrix[NMAX][NMAX];
int R , C;
int solutie[NMAX];
int sum_linii[NMAX] , aux_sum_linii[NMAX];
int sum_matrix = 0;
int max_suma = -1;
ifstream input("elimin.in");
ofstream output("elimin.out");
void backtrack(int pos)
{
if (pos > C)
{
int sum = 0;
for (int i = 0;i<nr_linii;i++)
{
aux_sum_linii[i] = 0;
for (int j = 1;j<pos;j++)
{
sum += matrix[i][solutie[j]];
aux_sum_linii[i] += matrix[i][solutie[j]];
}
aux_sum_linii[i] = sum_linii[i] - aux_sum_linii[i];
}
sort(aux_sum_linii , aux_sum_linii + nr_linii);
for (int i = 0;i<R;i++)
sum += aux_sum_linii[i];
if (sum_matrix - sum > max_suma)
max_suma = sum_matrix - sum;
}
else
{
for (int i = solutie[pos-1] + 1;i<nr_coloane;i++)
{
solutie[pos] = i;
backtrack(pos+1);
}
}
}
int main(int argc , char ** argv)
{
input >> nr_linii >> nr_coloane >> R >> C;
if (nr_linii > nr_coloane)
{
for (int i = 0;i<nr_linii;i++)
for (int j = 0;j<nr_coloane;j++)
input >> matrix[i][j];
}
else
{
for (int i = 0;i<nr_linii;i++)
for (int j = 0;j<nr_coloane;j++)
input >> matrix[j][i];
swap(nr_linii , nr_coloane);
swap(R , C);
}
int sum = 0;
for (int i = 0;i<nr_linii;i++)
{
sum = 0;
for (int j = 0;j<nr_coloane;j++)
{
sum_matrix += matrix[i][j];
sum += matrix[i][j];
}
sum_linii[i] += sum;
}
solutie[0] = -1;
backtrack(1);
output << max_suma;
input.close();
output.close();
return 0;
}