Cod sursa(job #1750452)

Utilizator PaulCbnCiobanu Paul PaulCbn Data 30 august 2016 11:47:19
Problema Elimin Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <iostream>
#include <cstdio>
#include <algorithm>
#define NMAX 8000
using namespace std;

int N,M,C,R;
int a[NMAX][NMAX];
int ok,smax=0;
int x[NMAX];

void citire()
{
    scanf("%d%d%d%d",&N,&M,&R,&C);

    ok=0; ///back elim randuri
    if(N-R < M-C)
    {
        ok=1;
        swap(N,M);
        swap(C,R);
    }
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++)
        {
            int x;
            scanf("%d",&x);
            if(ok==0)
                a[i][j]=x;
            else
                a[j][i]=x;
        }
}
int scol[NMAX];
int fol[NMAX];
void verif()
{
    for(int i=1; i<=N; i++)
            fol[i]=0;
    for(int i=1; i<=M; i++)
            scol[i]=0;

    for(int i=1; i<=R; i++)
        fol[x[i]]=1;


     for(int i=1;i<=N;i++)
        if(fol[i]==0)
            for(int j=1;j<=M;j++)
                scol[j]+=a[i][j];

    int sum=0;
    sort(scol+1,scol+M+1);
    for(int i=C+1;i<=M;i++)
        sum+=scol[i];
    smax = max(sum,smax);


}


void rezolvare()
{

    for(int i=1; i<=R; i++)
        x[i]=i;
    int k=R;
    while(k)
    {
        verif();
        k=R;
        while(x[k]>=N - (R-k) && k)
            k--;
        if(k==0)
            return;
        x[k]++;
        for(int i=k+1; i<=R; i++)
            x[i]=x[i-1]+1;
    }

}

int main()
{
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    citire();
    rezolvare();
    cout<<smax;

    return 0;
}