Cod sursa(job #1188429)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 19 mai 2014 18:01:34
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("elimin.in");
ofstream out("elimin.out");
 
const int nmax = 17, mmax = 7296;
int n, m, r, c, rasp = -(1<<30), mat[nmax][mmax];
bool avem[ nmax];
int aux[mmax];
 
void bkt(int x, int ram) {
    avem[x] = 1;

    if(ram>0)
	{
        for(int i = x + 1; i<=n - ram + 1; ++i)
		{
            bkt(i, ram - 1);
        }
    } 
	else
	{
        int s = 0;
        for(int j = 1; j<=m; ++j)
		{
            aux[j] = 0;

            for(int i = 1; i<=n; ++i)
			{
                if(avem[i]==0)
				{
                    aux[j] += mat[i][j];
                }
            }
            s += aux[j];
        }

        sort(aux + 1, aux + m + 1);

        for(int i = 1; i<=c; ++i)
		{
            s -= aux[i];
        }

        if (s>rasp)
		{
            rasp = s;
        }
    }

    avem[x] = 0;
}

int main()
{
	int player_unu=0;
    in>>n>>m>>r>>c;
    if(n>15) 
	{
        for(int i = 1; i<=n; ++i)
		{
            for(int j = 1; j<=m; ++j)
			{
                in>>mat[j][i];
            }
        }

		swap(n, m);
		swap(r, c);
    } 
	else
	{
        for(int i = 1; i<=n; ++i)
		{
            for( int j = 1; j <= m; ++j)
			{
                in>>mat[i][j];
            }
        }
    }

    bkt(0, r);

    out<<rasp<<'\n';
    return player_unu;
}