Cod sursa(job #2277811)

Utilizator JigsawKillerPetrescu Alexandru JigsawKiller Data 6 noiembrie 2018 21:07:59
Problema Elimin Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <fstream>
#define MAX 100

using namespace std;
int a[MAX][MAX], sumeL[MAX], sumeC[MAX], linii[MAX], coloane[MAX], suma, Max;

int verificare_linii(int r)
{
    int i;

    for(i = 1; i < r; i++)
        if(linii[i] >= linii[i + 1])return false;

    return true;
}

int verificare_coloane(int c)
{
    int i;

    for(i = 1; i < c; i++)
        if(coloane[i] >= coloane[i + 1])return false;

    return true;
}

int eliminareSuma(int r, int c)
{
    int i, j, suma = 0;

    for(i = 1; i <= r; i++)suma += sumeL[linii[i]];
    for(j = 1; j <= c; j++)suma += sumeC[coloane[j]];

    for(i = 1; i <= r; i++)
        for(j = 1; j <= c; j++)
            suma -= a[linii[i]][coloane[j]];

    return suma;
}

void backtracking_coloane(int m, int r, int c, int k)
{
    int i;

    if(k <= c)
    {
        for(i = 1; i <= m; i++)
        {
            coloane[k] = i;
            if(verificare_coloane(k))backtracking_coloane(m, r, c, k + 1);
        }
    }
    else
    {
        int sumaEliminare = eliminareSuma(r, c);
     //   cout << linii[1] << " " << coloane[1] << " " << sumaEliminare << endl;

        if(Max < suma - sumaEliminare)Max = suma - sumaEliminare;
    }
}

void backtracking_linii(int n, int m, int r, int c, int k)
{
    int i;

    if(k <= r)
    {
        for(i = 1; i <= n; i++)
        {
            linii[k] = i;
            if(verificare_linii(k))backtracking_linii(n, m, r, c, k + 1);
        }
    }
    else
    {
        backtracking_coloane(m, r, c, 1);
    }
}
int main()
{
    int n, m, r, c, i, j;

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

    fin >> n >> m >> r >> c;

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            suma += a[i][j];
        }

    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
        {
            sumeL[i] += a[i][j];
            sumeC[j] += a[i][j];
        }

    backtracking_linii(n, m, r, c, 1);

    fout << Max;

    fin.close();
    fout.close();

    return 0;
}