Cod sursa(job #1641979)

Utilizator FlorinHajaFlorin Gabriel Haja FlorinHaja Data 9 martie 2016 11:52:45
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>

using namespace std;

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

int a[280][280], n, m, i, j, r, c;
int sl[280], sc[280], st, sn;
int gl[280], gc[280], max1 = -2100000000;

void bkt(int k, int t)
{
    int i, j;
    if (k == r+1)
    {
        if (t == c+1)
        {
            sn = st;
            for (i = 1; i <= r; i++)
                sn -= sl[gl[i]];
            for (i = 1; i <= c; i++)
                sn -= sc[gc[i]];

            for (i = 1; i <= r; i++)
                for (j = 1; j <= c; j++)
                    sn += a[gl[i]][gc[j]];
            if (sn > max1)
                max1 = sn;
        }
        else
        {
            for (i = gc[t-1]+1; i <= m; i++)
            {
                gc[t] = i;
                bkt(k, t+1);
            }
        }
    }
    else
    {
        for (i = gl[k-1]+1; i <= n; i++)
        {
            gl[k] = i;
            bkt(k+1, t);
        }
    }
}

int main()
{
    f >> n >> m >> r >> c;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            f >> a[i][j];
            st += a[i][j];
            sl[i] += a[i][j];
            sc[j] += a[i][j];
        }

    bkt(1, 1);
    g << max1;
    return 0;
}