Cod sursa(job #2778026)

Utilizator doru.nituNitu Doru Constantin doru.nitu Data 27 septembrie 2021 18:07:31
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<fstream>
#include<algorithm>
using namespace std;

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

int r,n,m,c, k[1024];
int a[1024][1024];
int smax;
int M,R,row;

void verif()
{
    if(row)
    {
        int scol[1024];
        for(int col = 1; col<=n; ++col)
        {
            scol[col] = 0;
            for(int j = 1; j<=m; ++j)
                scol[col] += a[j][col];

            for(int j = 1; j<=R;++j)
                scol[col] -= a[k[j]][col];
        }

        sort(scol+1, scol+n+1);

        int smax_c = 0;
        for(int j=c+1; j<=n; ++j)
            smax_c += scol[j];

        if(smax_c > smax)
            smax = smax_c;
    }
    else
    {
        int srow[1024];
        for(int rr = 1; rr<=m; ++rr)
        {
            srow[rr] = 0;
            for(int j = 1; j<=n; ++j)
                srow[rr] += a[rr][j];

            for(int j = 1; j<=R; ++j)
                srow[rr] -= a[rr][k[j]];
        }

        sort(srow+1, srow+m+1);
        int smax_c = 0;
        for(int j=r+1; j<=m; ++j)
            smax_c += srow[j];

        if(smax_c > smax)
            smax = smax_c;
    }
}

void back(int i)
{
    if(i>R)
    {
        verif();
        return;
    }

    for(int j = k[i-1]+1; j<=M; ++j)
     {
         k[i] =j;
         back(i+1);
     }
}


int main()
{
    f>>m>>n>>r>>c;
    
    for(int i  =1; i<=m; ++i)
        for(int j = 1; j<=n; ++j)
            f>>a[i][j];

    if(m<n)
    {
        row = 1;
        M=m;
        R=r;
    }
    else
    {
        row = 0;
        M=n;
        R=c;
    }

    back(1);

    g<<smax<<"\n";

    
    return 0;
}