Pagini recente » Cod sursa (job #3208074) | Cod sursa (job #1055455) | Cod sursa (job #3246293) | Cod sursa (job #357330) | Cod sursa (job #1723829)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
struct pereche {
int index;
int suma;
};
int cmp_pereche_by_sum(pereche p1, pereche p2) {
return p1.suma < p2.suma;
}
int* malloc_array(int Size) {
int *arr = new int[Size];
for (int i = 0; i < Size; i++)
arr[i] = 0;
return arr;
}
int** malloc_matrix(int NumRows, int NumCols)
{
int** mat = new int*[NumRows];
for (int i = 0; i < NumRows; i++)
{
mat[i] = malloc_array(NumCols);
}
return mat;
}
int NumRows, NumCols;
int NumRowsEliminated, NumRowsSelected;
int NumColsEliminated, NumColsSelected;
int *sol, **mat, *sum_col;
int S;
void back_eliminate(int pos)
{
if (pos == NumRowsEliminated + 1)
{
pereche cols[NumCols];
for (int col = 0; col < NumCols; col++)
{
cols[col].index = col;
cols[col].suma = sum_col[col];
}
for (int i = 1; i <= NumRowsEliminated; i++)
{
int row = sol[i];
for (int col = 0; col < NumCols; col++)
{
cols[col].suma -= mat[row][col];
}
}
sort(cols, cols + NumCols, cmp_pereche_by_sum);
int s = 0;
for (int col = NumColsEliminated; col < NumCols; col++)
{
s += cols[col].suma;
}
if (s > S)
{
S = s;
}
return;
}
for (int row = sol[pos-1] + 1; row < NumRows; row++)
{
sol[pos] = row;
back_eliminate(pos + 1);
}
}
void back_select(int pos)
{
if (pos == NumRowsSelected + 1)
{
pereche cols[NumCols];
for (int col = 0; col < NumCols; col++)
{
cols[col].index = col;
cols[col].suma = 0;
}
for (int i = 1; i <= NumRowsSelected; i++)
{
int row = sol[i];
for (int col = 0; col < NumCols; col++)
{
cols[col].suma += mat[row][col];
}
}
sort(cols, cols + NumCols, cmp_pereche_by_sum);
int s = 0;
for (int col = NumCols - NumColsSelected; col < NumCols; col++)
{
s += cols[col].suma;
}
if (s > S)
{
S = s;
}
return;
}
for (int row = sol[pos-1] + 1; row < NumRows; row++)
{
sol[pos] = row;
back_select(pos + 1);
}
}
void gensub()
{
ifstream fi("elimin.in");
ofstream fo("elimin.out");
int M, N;
int R, C;
fi >> M >> N >> R >> C;
if (M < N)
{
mat = malloc_matrix(M, N);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
fi >> mat[i][j];
}
}
}
else
{
mat = malloc_matrix(N, M);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
fi >> mat[j][i];
}
}
int aux = M;
M = N;
N = aux;
aux = R;
R = C;
C = aux;
}
sol = malloc_array(M-R+1);
sum_col = malloc_array(N);
for (int i = 0; i < M; i++)
{
for (int j = 0; j < N; j++)
{
sum_col[j] += mat[i][j];
}
}
NumRows = M;
NumCols = N;
NumRowsEliminated = R;
NumColsEliminated = C;
NumRowsSelected = M - R;
NumColsSelected = N - C;
sol[0] = -1;
if (R > M - R)
back_eliminate(1);
else
back_select(1);
fo << S;
fi.close();
fo.close();
}
int main()
{
gensub();
return 0;
}