Cod sursa(job #2711238)

Utilizator HardtoPronouncePetcu David-Andrei HardtoPronounce Data 23 februarie 2021 19:57:49
Problema Elimin Scor 0
Compilator cpp-64 Status done
Runda simulare_nr1 Marime 1.22 kb

#include<iostream>
#include<fstream>

using namespace std;

ifstream f("elimin.in");
ofstream g("elimin.out");

int backrows[20],backcolumns[20];
int n, krows,m,kcolumns,summax;
short mat[1635][1635];
bool badrows[1635], badcolumns[1635];

void calculate_maxsum()
{
	//remove rows
	for (int i = 1; i <= krows; i++)
		badrows[backrows[i]] = true;
	//remove columns
	for (int i = 1; i <= kcolumns; i++)
		badrows[backcolumns[i]] = true;
	//calculate sum
	int sum = 0;
	for (int i = 1; i <= n; i++)
		if (badrows[i] == false)
			for (int j = 1; j <= m; j++)
				if (badcolumns[j] == false)
					sum += mat[i][j];
	if (sum > summax)
		summax = sum;
}

void back_for_columns(int p)
{
	for (int i = backcolumns[p - 1] + 1; i <= m; i++)
	{
		backcolumns[p] = i;
		if (p == kcolumns)
			calculate_maxsum();
		else
			back_for_columns(p + 1);
	}
}

void back_for_rows(int p)
{
	for (int i = backrows[p - 1] + 1; i <= n; i++)
	{
		backrows[p] = i;
		if (p == krows)
			back_for_columns(1);
		else
			back_for_rows(p + 1);
	}
}


int main()
{
	f >> n >> m >> krows >> kcolumns;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			f >> mat[i][j];
	back_for_rows(1);
	g << summax;
}