Cod sursa(job #1113006)

Utilizator StanAndreiAndrei Stan StanAndrei Data 20 februarie 2014 11:17:18
Problema Elimin Scor 10
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2013 Marime 1.53 kb
#include <stdio.h>
#include <vector>

#define NMAX 7295
#define INF 0x3f3f3f3f

using namespace std;

vector<int> A[NMAX];
bool x[NMAX],y[NMAX];

int N,M,R,C;

void read()
{
    scanf("%d %d %d %d\n",&M,&N,&R,&C);
    int x;
    for (int i=1;i<=M;i++)
        for (int j=1;j<=N;j++)
        {
            scanf("%d ",&x);
            A[i].push_back(x);
        }
}

void findline()
{
    int sum,line,min=INF;
    for (int i=1;i<=M;i++)
    {
        sum=0;
        if (!x[i])
            for (int j=0;j<A[i].size();j++)
                if (!y[j]) sum+=A[i][j];
        if (sum<min)
        {
            min=sum;
            line=i;
        }
    }
    x[line]=1;
    R--;
}

void findcolumn()
{
    int sum,column,min=INF,j;
    j=0;
    while (j<N)
    {
        sum=0;
        for (int i=1;i<=M;i++)
            if (!x[i] && !y[j]) sum+=A[i][j];
        if (sum<min)
        {
            min=sum;
            column=j;
        }
        j++;
    }

    y[column]=1;
    C--;
}

void solve()
{
    while (R || C)
    {
        if (R)
            findline();
        if (C)
            findcolumn();
    }

    int sum=0;
    for (int i=1;i<=M;i++)
    {
        if (!x[i])
            for (int j=0;j<A[i].size();j++)
                if (!y[j]) sum+=A[i][j];
    }
    printf("%d\n",sum);
}

int main()
{
    freopen ("elimin.in","r",stdin);
    freopen ("elimin.out","w",stdout);

    read();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}