Cod sursa(job #2417091)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 28 aprilie 2019 21:02:09
Problema Elimin Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

//ifstream in("elimin.in");
ofstream out("elimin.out");

class InParser {
	
private:
	FILE *fin;
	
	char *buff;
	int sp;
	
	char read_ch() 
	{
		sp++;
	
		if(sp == 4096) 
		{
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
	
		return buff[sp];
	}
	
public:
	
	InParser(const char* nume) 
	{
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) 
	{
		char c;
	
		while (!isdigit(c = read_ch()) && c != '-');

		if(c == '-') 
		{
			n = 0;
		} 
		else 
		{
			n = c - '0';
		}
	
		while(isdigit(c = read_ch())) 
		{
			n = 10 * n + c - '0';
		}
	
		return *this;
	}
};

const int DIM = 8000;

int v[DIM][DIM];
int t[DIM][DIM];

int p[DIM];
int ps[DIM];

int best = 0;
int sum = 0;

int n, m;

bitset <DIM> vis;

void rotate()
{
	for(int i = m; i >= 1; i--)
		for(int j = 1; j <= n; j++)
			t[m - i + 1][j] = v[j][i];
	
	for(int i = 1; i <= m; i++)
		for(int j = 1; j <= n; j++)
			v[i][j] = t[i][j];
}

bool cmp(int a, int b)
{
	if(ps[a] <= ps[b])
		return true;
	
	return false;
}

int r, c;

void back(int r, int c, int last)
{
	if(r == 0)
	{
		sort(p + 1, p + 1 + m, cmp);
		
		int s = 0;
		
		for(int j = c + 1; j <= m; j++)
			s += ps[p[j]];
		
		best = max(best, s);
	}
	else
	{
		for(int i = last + 1; i <= n && n - i >= r - 1; i++)
			if(vis[i] == 0)
			{
				vis[i] = 1;
				
				for(int j = 1; j <= m; j++)
					ps[j] -= v[i][j];
				
				back(r - 1, c, i);
				
				for(int j = 1; j <= m; j++)
					ps[j] += v[i][j];
				
				vis[i] = 0;
			}
	}
}

main()
{
	InParser fin("elimin.in");
	
	fin >> n >> m >> r >> c;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			fin >> v[i][j];
			
			sum += v[i][j];
		}
		
	if(n > m)
	{
		rotate();
		swap(n, m);
		swap(r, c);
	}
	
	for(int i = 1; i <= m; i++)
		p[i] = i;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			ps[j] += v[i][j];
	
	back(r, c, 0);
	
	out << best;
}