Pagini recente » Cod sursa (job #1593661) | Cod sursa (job #2064336) | Cod sursa (job #2669480) | Cod sursa (job #77858) | Cod sursa (job #2313126)
#include <stdio.h>
#include <algorithm>
using namespace std;
int matrice[20][10005],suma,aux, n, m,c, r, rezultat = -99999999, nr[100005], v[20];
void suma_elementelor()
{
nr[0] = 0;
//calculez suma pe fiecare coloana in parte
for(int j = 1; j <= n; j++)
{
suma = 0;
for(int i = 1; i <= m; i++)
if(v[i] == 0)
suma = suma + matrice[i][j];
// nr[0]++;
//pastrez intr-un vector suma pe fiecare coloana
nr[++nr[0]] = suma;
}
//sortez vectorul incepand cu prima pozitie pana la nr total de sume
sort(nr + 1, nr + 1 +nr[0]);
suma =0;
//fac suma sumelor ramaseincepand de la nr coloanei c pana la nr de sume
for(int i = c +1; i <= nr[0]; i++)
suma = suma + nr[i];
if(rezultat < suma)
rezultat = suma;
}
void backtracking(int x, int y)
{
for(int i = 0; i < 2; i++)
{
v[x] = i;
//daca am ajuns in varful stivei, nu mai pot adauga
if(x == m)
{
if(y + v[x] == r)
suma_elementelor();
}
else backtracking(x + 1, y + v[x]);
}
}
int main()
{
FILE *f = fopen("elimin.in", "r+");
FILE *g = fopen("elimin.out", "w+");
fscanf(f, "%d%d%d%d", &m, &n, &r, &c);
if(m > n)
{for(int i = 1; i<= m; i++)
for(int j = 1; j <= n; j++)
//citesc matricea invers, incepand cu ultima coloana
fscanf(f, "%d", &matrice[j][m - i + 1]);
aux = m;
m = n;
n = aux;
aux = r;
r = c;
c = aux;
}
else{
for(int i = 1; i<= m; i++)
for(int j = 1; j<= n; j++)
fscanf(f, "%d", &matrice[i][j]);
}
backtracking(1, 0);
fprintf(g, "%d ", rezultat);
return 0;
}