Cod sursa(job #546177)

Utilizator noemirkNoemi Noemi noemirk Data 4 martie 2011 16:01:17
Problema Elimin Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <vector>
#include <fstream>
#include <stdio.h>
using namespace std;
//ifstream fi("elimin.in");
FILE * fi;
ofstream fo("elimin.out");
int n,m,i,j,a;
int R,C;
vector <int> V[7300];
int S[100];
int OK[100];
int SC[10000],SL[10000];
int rez;

void gl(int k)
{
    int i,j,suma;
    vector <int> :: iterator it;
    if (k==R)
    {
        for (i=1;i<=n;i++)
            OK[i]=1;
        for (i=1;i<=R;i++)
            OK[S[i]]=0;
        for (i=1;i<=m;i++)
            SC[i]=0;
        for (i=1;i<=n;i++)
            if (OK[i]==1)
            {
                j=0;
                for

(it=V[i].begin();it!=V[i].end();it++)
                {
                    j++;
                    SC[j]+=(*it);
                }
            }
        sort(SC+1,SC+m+1);
        suma=0;
        for (i=C+1;i<=m;i++)
            suma+=SC[i];
        if (suma>rez)
            rez=suma;
    }
    else
        for (i=S[k]+1;i<=n;i++)
        {
            S[k+1]=i;
            gl(k+1);
        }
}

void gc(int k)
{
    int i,j,suma;
    vector <int> :: iterator it;
    if (k==C)
    {
        for (i=1;i<=m;i++)
            OK[i]=1;
        for (i=1;i<=C;i++)
            OK[S[i]]=0;
        for (i=1;i<=m;i++)
            SL[i]=0;
        for (i=1;i<=m;i++)
            if (OK[i]==1)
            {
                j=0;
                for

(it=V[i].begin();it!=V[i].end();it++)
                {
                    j++;
                    SL[j]+=(*it);
                }
            }
        sort(SL+1,SL+m+1);
        suma=0;
        for (i=R+1;i<=n;i++)
            suma+=SL[i];
        if (suma>rez)
            rez=suma;
    }
    else
        for (i=S[k]+1;i<=m;i++)
        {
            S[k+1]=i;
            gc(k+1);
        }
}

int main()
{
	fi=fopen("elimin.in","r");
    fscanf(fi,"%d%d%d%d",&n,&m,&R,&C);
    if (n<=m)
    {
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++)
            {
                fscanf(fi,"%d",&a);
                V[i].push_back(a);
            }
        rez=-1;
        gl(0);
        fo<<rez;
    }
    else
    {
        for (i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                fscanf(fi,"%d",&a);
                V[j].push_back(a);
            }
        rez=-1;
        gc(0);
        fo<<rez;
    }
    fclose(fi);
    fo.close();
    return 0;
}