Cod sursa(job #2216415)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 26 iunie 2018 17:36:31
Problema Elimin Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include<bits/stdc++.h>
#define MAX 7299

using namespace std;

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

int matrice[MAX][555],n,m,col,linii,suma_linii[MAX];
int stiva[555],solutie;
int sMax;
void citire()
{
    f>>n>>m>>linii>>col;

    if(n<m)
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
        {
            f>>matrice[j][i];
            suma_linii[j]+=matrice[j][i];
        }
        int aux=n;
        n=m;
        n=aux;

        aux=linii;
        linii=col;
        col=aux;
    }
    else
    {
        for(int i=1;i<=n;++i)
            for(int j=1;j<=m;++j)
        {
            f>>matrice[i][j];
            suma_linii[i]+=matrice[i][j];
        }
    }

}

void sumaMax()
{
    for(int i=1;i<=n;++i)
        sMax+=suma_linii[i];
}

void fara()
{
    sort(suma_linii+1,suma_linii+1+n);

    for(;linii;--linii)
        sMax-=suma_linii[linii];

    g<<sMax;

}

void cuBCK(int k)
{
    for(int i=stiva[k+1];i<=m;++i)
    {
        stiva[k]=i;

        for(int j=1;j<=n;++j)
        {
            sMax-=matrice[j][i];
            suma_linii[j]-=matrice[j][i];
        }

            if(k==col)
            {
                int valid[MAX];
                for(int j=1;j<=n;++j)
                    valid[j]=suma_linii[j];
                sort(valid+1,valid+n+1);
                int sumaV=sMax;
                for(int j=1;j<=linii;++j)
                    sumaV-=suma_linii[j];
                solutie=max(solutie,sumaV);
            }
            else
                cuBCK(k+1);



        for(int j=1;j<=n;++j)
        {
            sMax+=matrice[j][i];
            suma_linii[j]+=matrice[j][i];
        }
    }
}
int main()
{
    citire();
    sumaMax();
    if(col==0)
    {
        fara();
        return 0;
    }
    else
        cuBCK(1);
    g<<solutie;
    return 0;
}