Cod sursa(job #2061297)

Utilizator donydony2010George Donisan donydony2010 Data 9 noiembrie 2017 03:16:31
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

struct SumEntry{
	SumEntry(int val, int index) : m_Value(val), m_Index(index){}
	int m_Value;
	int m_Index;
};

bool CompareSumEntry(const SumEntry& a, const SumEntry& b)
{
	return a.m_Value < b.m_Value;
}

int ExtraWeightRemoveColumn(const vector<vector<short>>& matrix, const vector<SumEntry>& columns, const vector<SumEntry>& rows, int index, int rowsToBeRemoved)
{
	vector<SumEntry> newRows(rows);
	for(int i = 0; i < newRows.size(); i++)
	{
		newRows[i].m_Value -= matrix[i][index];
	}

	sort(newRows.begin(), newRows.end(), CompareSumEntry);

	int sum = 0;
	for(int i = 0; i < rowsToBeRemoved; i++)
	{
		sum += newRows[i].m_Value;
	}
	return sum;
}

void RemoveColumn(const vector<vector<short>>& matrix, vector<SumEntry>& columns, vector<SumEntry>& rows, int index)
{
	for(int i = 0; i < rows.size(); i++)
	{
		rows[i].m_Value -= matrix[i][index];
	}

	columns.erase(columns.begin() + index);
}

int main()
{
	vector<vector<short>> matrix;
	int m, n, r, c;
	ifstream f("elimin.in");
	ofstream g("elimin.out");
	f >> m >> n >> r >> c;

	for(int i = 0; i < m; i++)
	{
		matrix.push_back(vector<short>());
		for(int j = 0; j < n; j++)
		{
			short x;
			f >> x;
			matrix[i].push_back(x);
		}
	}

	int columnsFound = 0;
	int rowsFound = 0;

	vector<SumEntry> columnSum(n, SumEntry(0, 0));
	vector<SumEntry> rowSum(m, SumEntry(0, 0));

	for(int i = 0; i < m; i++)
	{
		for(int j = 0; j < n; j++)
		{
			columnSum[j].m_Value += matrix[i][j];
			rowSum[i].m_Value += matrix[i][j];
			columnSum[j].m_Index = j;
			rowSum[i].m_Index = i;
		}
	}

	for(int i = 0; i < c; i++)
	{
		int minIndex = 0;
		int min = 0x3f3f3f3f;
		for(int j = 0; j < columnSum.size(); j++)
		{
			int sum = columnSum[j].m_Value + ExtraWeightRemoveColumn(matrix, columnSum, rowSum, columnSum[j].m_Index, r);
			if(min > sum)
			{
				min = sum;
				minIndex = j;
			}
		}
		RemoveColumn(matrix, columnSum, rowSum, minIndex);
	}
	
	sort(rowSum.begin(), rowSum.end(), CompareSumEntry);

	int sum = 0;
	for(int i = r; i < m; i++)
	{
		sum += rowSum[i].m_Value;
	}
	g << sum;
}