Cod sursa(job #13540)

Utilizator sims_glAlexandru Simion sims_gl Data 6 februarie 2007 23:04:32
Problema Elimin Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define nm 1024

void go(int);

int n, m, r, c, used[nm], v[nm], s[nm], crt, sol;
short int a[nm][nm];

int main()
{
	int i, j;

	freopen("elimin.in", "r", stdin);
    freopen("elimin.out", "w", stdout);

    scanf("%d%d", &n, &m);

    if (n < m)
    {
    	n += m;
        m = n - m;
        n -= m;
    
    	scanf("%d%d", &c, &r);

        for (i = 1; i <= m; ++i)
        	for (j = 1; j <= n; ++j)
            	scanf("%d", &a[j][i]);
    }
    else
    {
    	scanf("%d%d", &r, &c);

        for (i = 1; i <= n; ++i)
        	for (j = 1; j <= m; ++j)
            	scanf("%d", &a[i][j]);
    }

    go(1);

    printf("%d\n", sol);

	return 0;
}

void go(int pos)
{
	int i, j;

    if (pos > c)
    {
		for (i = 1; i <= n; i += 5)
        	for (s[i] = s[i + 1] = s[i + 2] = s[i + 3] = s[i + 4] = 0, j = 1; j <= m; ++j)
    			if (!used[j])
                {
                	s[i] += a[i][j];
                    s[i + 1] += a[i + 1][j];
                    s[i + 2] += a[i + 2][j];
                    s[i + 3] += a[i + 3][j];
                    s[i + 4] += a[i + 4][j];
                }

        sort(s + 1, s + n + 1);

        for (crt = 0, i = r + 1; i <= n; ++i)
        	crt += s[i];

        if (sol < crt)
        	sol = crt;
    }
    else
    {
    	for (i = v[pos - 1] + 1; i <= m - c + pos; ++i)
        {
        	v[pos] = i;
            used[i] = 1;

            go(pos + 1);

            used[i] = 0;
        }
    }
}