Cod sursa(job #2417082)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 28 aprilie 2019 20:53:31
Problema Elimin Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

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

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()
{
	in >> n >> m >> r >> c;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
		{
			in >> 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;
}