Pagini recente » Cod sursa (job #1361590) | Cod sursa (job #1506515) | Cod sursa (job #1764440) | Cod sursa (job #1830780) | Cod sursa (job #1751069)
#include <stdio.h>
#include <algorithm>
using namespace std;
int m,n,r,c;
int mat[88][2000];
int suma_linie[88];
int suma_coloana[2000];
int combinari[88];
int suma_totala;
int suma_maxima;
int suma_curenta;
bool linie_taiata[88];
void read()
{
freopen("elimin.in","r",stdin);
freopen("elimin.out","w",stdout);
scanf("%d %d %d %d ",&m,&n,&r,&c);
if(n < m)
{
swap(n,m);
swap(r,c);
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
{
scanf("%d ",&mat[i][j]);
suma_linie[i] += mat[i][j];
}
}
else
{
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
{
scanf("%d",&mat[i][j]);
suma_linie[i] += mat[i][j];
}
}
for(int i = 0; i < m ; i++)
suma_totala += suma_linie[i];
}
void reset()
{
for(int i = 0 ; i < m ; i++)
linie_taiata[i] = false;
for(int i = 0 ; i < n ; i++)
suma_coloana[i] = 0;
}
void suma()
{
suma_curenta = suma_totala;
for(int i = 0 ; i < r; i++)
{
int linie = combinari[i] - 1;
suma_curenta -= suma_linie[linie];
linie_taiata[linie] = true;
}
for(int j = 0 ; j < n ; j++)
{
for(int i = 0 ; i < m ; i++)
if(linie_taiata[i] == false)
suma_coloana[j] += mat[i][j];
}
sort(suma_coloana,suma_coloana + n);
for(int i = 0 ; i < c ; i++)
suma_curenta -= suma_coloana[i];
if(suma_curenta > suma_maxima)
suma_maxima = suma_curenta;
reset();
}
void rezolv()
{
for(int i = 0 ; i < r ; i++)
combinari[i]= i + 1;
int i = r - 1;
int dif = 0;
int pozitie = i;
while(i > -1)
{
if(combinari[i] == m - dif)
{
dif++;
pozitie = i;
i--;
continue;
}
if( i < pozitie)
{
suma();
combinari[i]++;
i++;
for( i ; i < r ; i++)
combinari[i] = combinari[i - 1] + 1;
dif = 0;
i--;
pozitie = i;
continue;
}
if( combinari[i] < n - dif)
{
suma();
combinari[i]++;
continue;
}
}
suma();
if(suma_curenta > suma_maxima)
suma_maxima = suma_curenta;
printf("%d",suma_maxima);
}
int main()
{
read();
rezolv();
return 0;
}