Cod sursa(job #2037780)

Utilizator modulopaulModulopaul modulopaul Data 12 octombrie 2017 19:30:31
Problema Elimin Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <cstdio>
#define MAXNM 3647
#define sh short

using namespace std;
FILE *fin=fopen("elimin.in","r"),*fout=fopen("elimin.out","w");
sh n,m,R,C,mt[MAXNM][MAXNM],r[MAXNM],c[MAXNM],st[MAXNM];
int ts,maxs;
void calc(){
    int tst=ts;
    for(int i=1;i<=R;i++){
        tst-=r[st[i]];
    }
    for(int i=R+1;i<=R+C+1;i++){
        tst-=c[st[i]];
    }
    for(int i=1;i<=R;i++){
        for(int j=R+1;j<=R+C+1;j++){
            tst+=mt[st[i]][st[j]];
        }
    }
    if(tst>maxs) maxs=tst;
}
void bt(sh niv){
    if(niv>R+C+1){
        calc();
    }
    else if(niv<=R){
        for(sh i=st[niv-1]+1;i<=n;i++){
            st[niv]=i;
            bt(niv+1);
        }
    }
    else{
        if(niv==R+1) niv++;
        for(sh i=st[niv-1]+1;i<=m;i++){
            st[niv]=i;
            bt(niv+1);
        }
    }
}
int main(){
    fscanf(fin,"%hd",&n);
    fscanf(fin,"%hd",&m);
    fscanf(fin,"%hd%hd",&R,&C);
    for(sh i=1;i<=n;i++){
        for(sh j=1;j<=m;j++){
            fscanf(fin,"%hd",&mt[i][j]);
            r[i]+=mt[i][j];
            c[j]+=mt[i][j];
            ts+=mt[i][j];
        }
    }
    bt(1);
    fprintf(fout,"%d",maxs);
    return 0;
}