Pagini recente » Cod sursa (job #548926) | Cod sursa (job #2683683) | Cod sursa (job #328206) | Cod sursa (job #417327) | Cod sursa (job #1747760)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int r, c;
int mat[20][20];
int sumeLinie[20];
int sumeColoane[20];
vector<int> sol;
int solx[20];
int maxSuma = 999999;
int sumaInitiala;
void citire()
{
scanf("%d %d %d %d", &n, &m, &c, &r);
if(n <= m)
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%d", &mat[i][j]);
sumaInitiala += mat[i][j];
sumeLinie[i] += mat[i][j];
}
}
}
else
{
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
scanf("%d", &mat[j][i]);
sumaInitiala += mat[j][i];
sumeLinie[j] += mat[j][i];
}
}
swap(n, m);
swap(r, c);
}
}
void calculareSuma()
{
int suma = sumaInitiala;
if(sol.size() > r)
{
return;
}
for(int i = 0; i < 20; i++)
{
solx[i] = 0;
}
for(int i = 0; i < sol.size(); i++)
{
suma -= sumeLinie[sol[i]];
solx[sol[i]] = 1;
}
int tmp1;
vector<int> tmpx;
for(int i = 0; i < m; i++)
{
tmp1 = 0;
for(int j = 0; j < n; j++)
{
if(solx[j] == 0)
{
tmp1 += mat[j][i];
}
else
{
tmp1 -= mat[j][i];
}
}
tmpx.push_back(tmp1);
}
sort(tmpx.rbegin(), tmpx.rend());
for(int i = c; i < m; i++)
{
suma -= tmpx[i];
}
if(suma < maxSuma)
{
maxSuma = suma;
}
}
void backtracking()
{
long long limita = ((long long)1 << (n));
for(long long k = 1; k < limita; k++)
{
sol.clear();
for(int i = 0; i <= 16; i++)
{
if((k & (1 << i)) != 0)
{
sol.push_back(i);
}
}
if(sol.size() != r)
{
continue;
}
calculareSuma();
}
printf("%d", maxSuma);
}
int main()
{
freopen("elimin.in", "r", stdin);
freopen("elimin.out", "w", stdout);
citire();
backtracking();
return 0;
}