Cod sursa(job #2277848)

Utilizator JigsawKillerPetrescu Alexandru JigsawKiller Data 6 noiembrie 2018 22:04:32
Problema Elimin Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <fstream>
#include <algorithm>
#define MAX 1000

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

void sortare(int r, int c, int m)
{
    int i, j;

    for(i = 1; i <= r; i++)
        for(j = 1; j <= m; j++)
            sumeC[j] -= a[linii[i]][j];

    for(j = 1; j <= m; j++)sume2C[j] = sumeC[j];
    sort(sume2C + 1, sume2C + 1 + m);

    int suma = 0;

    for(j = c + 1; j <= m; j++)suma += sume2C[j];

    if(Max < suma)Max = suma;

    for(i = 1; i <= r; i++)
        for(j = 1; j <= m; j++)
            sumeC[j] += a[linii[i]][j];
}

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

    if(k <= r)
    {
        for(i = 1; linii[k - 1] + i <= n; i++)
        {
            linii[k] = linii[k - 1] + i;
            backtracking(n, m, r, c, k + 1);
        }
    }
    else
    {
        sortare(r, c, m);

    }
}
int main()
{
    int n, m, l, c, i, j;

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

    fin >> n >> m >> l >> c;

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

    if(n > m){
        swap(n, m);
        swap(l, c);
    }

    backtracking(n, m, l, c, 1);

    fout << Max;

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

    return 0;
}