Cod sursa(job #1018037)

Utilizator RamaStanciu Mara Rama Data 28 octombrie 2013 20:12:57
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define MAX 8000
#define MIN 20

using namespace std;

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

int m, n, r, c, sum = 0, sf, maxim = 0;

int matrix[MIN][MAX], st[MIN], s_line[MIN], s_col[MAX], s_column[MAX], is[MIN];

void back(int k)
{
    if (k==r+1)
    {
        for (int i=1;i<=n;i++)
        {
            s_column[i] = s_col[i];
            for (int j=1;j<=m;j++)
            {
                if (is[j]!=0)
                {
                    s_column[i] -= matrix[j][i];
                }
            }
        }
        sort(s_column+1,s_column+n+1);
        sf = sum;
        for (int i=1;i<=c;i++)
        {
            sf-=s_column[i];
        }
        if (sf > maxim)
        {
            maxim = sf;
        }
    }
    else
    {
        for (int t=st[k-1]+1;t<=m;t++)
        {
            if (!is[t])
            {
                st[k] = t;
                is[t] = 1;
                sum -= s_line[t];
                back(k + 1);
                is[t] = 0;
                sum += s_line[t];
            }
        }
    }
}

int main()
{
    in>>m>>n>>r>>c;
    if (m<n)
    {
        for (int i=1;i<=m;i++)
        {
            for (int j=1;j<=n;j++)
            {
                in>>matrix[i][j];
                sum += matrix[i][j];
                s_line[i] += matrix[i][j];
                s_col[j] += matrix[i][j];
            }
        }
    }
    else
    {
        for (int i=1;i<=m;i++)
        {
            for (int j=1;j<=n;j++)
            {
                in>>matrix[n-j+1][i];
                sum+= matrix[n-j+1][i];
                s_line[n-j+1]+=matrix[n-j+1][i];
                s_col[i]+=matrix[n-j+1][i];
            }
        }
        int aux = m;
        m = n;
        n = aux;
        aux = c;
        c = r;
        r = aux;
    }

    back(1);
    out<<maxim;

    return 0;
}