Cod sursa(job #1061225)

Utilizator mariacMaria Constantin mariac Data 19 decembrie 2013 14:38:38
Problema Elimin Scor 90
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 2.37 kb
#include<vector>
#include<algorithm>
#include<fstream>
using namespace std;
int n, m, r, c, St;
int **a;
int *sumc, *suml;
int *v;
int smin = 320000000 ;

int greedy(bool linie)
{
    vector<int> h;
    int  i;
    if (linie)
    {
        for (i = 1; i <= m; i++)
            h.push_back(sumc[i]);
    }
    else
    {
        for (i = 1; i <= n; i++)
            h.push_back(suml[i]);
    }
    sort(h.begin(), h.end());
    int s = 0;
    if (linie)
    {
        for (i = 0; i < c; i++)
            s += h[i];
        return s;
    }
    else
    {
        for (i = 0; i < r; i++)
            s += h[i];
        return s;
    }
    h.clear();
}

void Back(int k, int nn, bool linie, int sum, int cate)
{

    int i;
    if(nn == 0)  smin = greedy(linie);
    else
        for (v[k] = v[k - 1] + 1; v[k] <= nn; v[k]++)
        {
            int s = 0;
            if (linie)
            {
                s = suml[v[k]];
                for (i = 1; i <= m; i++)
                    sumc[i] -= a[v[k]][i];
            }
            else
            {
                s = sumc[v[k]];
                for (i = 1; i <= n; i++)
                    suml[i] -= a[i][v[k]];
            }
            if (k == cate)
            {
                s += sum;
                s += greedy(linie);
                if (s < smin)
                    smin = s;
            }
            else
                Back(k + 1, nn, linie, sum + s, cate);
            if (linie)
                for (i = 1; i <= m; i++)
                    sumc[i] += a[v[k]][i];
            else
                for (i = 1; i <= n; i++)
                    suml[i] += a[i][v[k]];

        }


}

int main()
{

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

    fin>>n>>m>>r>>c;
    a = new int*[n+5];
    suml = new int[n+5];
    sumc = new int[m+5];
    for (int i = 1; i <= n; i++)
    {
        a[i] = new int[m+5];

        for (int j = 1; j <= m; j++)
        {
            fin>>a[i][j];
            St += a[i][j];
            suml[i] += a[i][j];
            sumc[j] += a[i][j];
        }
    }

    if (n < m)
    {
        v = new int[n+5];
        v[0] = 0;
        Back(1, n, true, 0, r);
    }
    else
    {
        v = new int[m+5];
        v[0] = 0;
        Back(1, m, false, 0, c);
    }
    fout<<St - smin;

}