Cod sursa(job #1723829)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 1 iulie 2016 16:38:59
Problema Elimin Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct pereche {
    int index;
    int suma;
};

int cmp_pereche_by_sum(pereche p1, pereche p2) {
    return p1.suma < p2.suma;
}

int* malloc_array(int Size) {
    int *arr = new int[Size];
    for (int i = 0; i < Size; i++)
        arr[i] = 0;
    return arr;
}

int** malloc_matrix(int NumRows, int NumCols)
{
    int** mat = new int*[NumRows];
    for (int i = 0; i < NumRows; i++)
    {
        mat[i] = malloc_array(NumCols);
    }
    return mat;
}

int NumRows, NumCols;
int NumRowsEliminated, NumRowsSelected;
int NumColsEliminated, NumColsSelected;
int *sol, **mat, *sum_col;
int S;

void back_eliminate(int pos)
{
    if (pos == NumRowsEliminated + 1)
    {
        pereche cols[NumCols];
        for (int col = 0; col < NumCols; col++)
        {
            cols[col].index = col;
            cols[col].suma = sum_col[col];
        }

        for (int i = 1; i <= NumRowsEliminated; i++)
        {
            int row = sol[i];

            for (int col = 0; col < NumCols; col++)
            {
                cols[col].suma -= mat[row][col];
            }
        }

        sort(cols, cols + NumCols, cmp_pereche_by_sum);

        int s = 0;

        for (int col = NumColsEliminated; col < NumCols; col++)
        {
            s += cols[col].suma;
        }

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

        return;
    }

    for (int row = sol[pos-1] + 1; row < NumRows; row++)
    {
        sol[pos] = row;

        back_eliminate(pos + 1);
    }
}

void back_select(int pos)
{
    if (pos == NumRowsSelected + 1)
    {
        pereche cols[NumCols];

        for (int col = 0; col < NumCols; col++)
        {
            cols[col].index = col;
            cols[col].suma = 0;
        }

        for (int i = 1; i <= NumRowsSelected; i++)
        {
            int row = sol[i];

            for (int col = 0; col < NumCols; col++)
            {
                cols[col].suma += mat[row][col];
            }
        }

        sort(cols, cols + NumCols, cmp_pereche_by_sum);

        int s = 0;

        for (int col = NumCols - NumColsSelected; col < NumCols; col++)
        {
            s += cols[col].suma;
        }

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

        return;
    }

    for (int row = sol[pos-1] + 1; row < NumRows; row++)
    {
        sol[pos] = row;

        back_select(pos + 1);
    }
}

void gensub()
{
    ifstream fi("elimin.in");
    ofstream fo("elimin.out");

    int M, N;
    int R, C;

    fi >> M >> N >> R >> C;

    if (M < N)
    {
        mat = malloc_matrix(M, N);

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                fi >> mat[i][j];
            }
        }
    }
    else
    {
        mat = malloc_matrix(N, M);

        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                fi >> mat[j][i];
            }
        }

        int aux = M;
        M = N;
        N = aux;

        aux = R;
        R = C;
        C = aux;
    }

    sol = malloc_array(M-R+1);
    sum_col = malloc_array(N);

    for (int i = 0; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            sum_col[j] += mat[i][j];
        }
    }

    NumRows = M;
    NumCols = N;
    NumRowsEliminated = R;
    NumColsEliminated = C;
    NumRowsSelected = M - R;
    NumColsSelected = N - C;

    sol[0] = -1;
    if (R > M - R)
        back_eliminate(1);
    else
        back_select(1);

    fo << S;

    fi.close();
    fo.close();
}

int main()
{
    gensub();

    return 0;
}