Cod sursa(job #2740250)

Utilizator NastureNasture Anca Nasture Data 12 aprilie 2021 11:28:50
Problema Elimin Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ( "elimin.in" );
ofstream cout ( "elimin.out" );
const int DIV_MAX = 15;
const int NMAX = 7294;
int a[DIV_MAX+1][NMAX+1];
int col[NMAX+1];
int ord[NMAX+1];
int n,m,r,c;
int st[DIV_MAX + 1];
int maxy = 0;
int sum_all (int m)
{
    int s = 0;
    for ( int i=1;i<= m;i++ )
        s += col[i];
    return s;
}
bool cmp ( int a, int b )
{
    return col[a] < col[b];
}
void bkt (int k)
{
    if (k==r+1)
    {
        sort(ord+1,ord+m+1,cmp);
        int s = sum_all (m);
        int smin = 0;
        for ( int i = 1; i <= c; i++)
            smin += col[ord[i]];
        if(s-smin>maxy)
            maxy=s-smin;
        return;
    }
    for ( int i = st[k - 1] + 1;i<=n-(r - k);i++ )
    {
        st[k] = i;
        for (int j = 1;j<= m;j++ )
            col[j] -= a[i][j];
        bkt ( k + 1 );
        for (int j = 1;j<=m;j++ )
            col[j] += a[i][j];
    }
}

int main() {
    int i, j, aux;
    cin>>n>>m>>r>>c;

    if (n<m)
        for (i=1;i<=n;i++)
            for (j=1;j<=m;j++ )
                cin >> a[i][j];
    else
    {
        for(i = 1;i<= n;i++)
            for(j=1;j<= m;j++ )
                cin>>a[j][i];
        aux=n;
        n=m;
        m=aux;
        aux=r;
        r=c;
        c=aux;
    }

    for (i=1;i<=m;i++)
        ord[i]=i;

    for(i=1;i<=n;i++ )
        for (j=1;j<=m;j++ )
            col[j]+=a[i][j];
    st[0] = -1;
    bkt ( 1 ); // nu am facut cu descompunerea in baza 2 deoarece
    // trebuia sa verificam pt fiecare indice nr de biti 1
    cout << maxy;

    return 0;
}