Cod sursa(job #1928547)

Utilizator tgm000Tudor Mocioi tgm000 Data 16 martie 2017 15:01:46
Problema Elimin Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int a[16][7295];
int l[7295];
int v[7295];
int n,m,r,c;
int maxi;
int solve(){
    int s=0,j,i;
    for(j=1;j<=m;j++){
        v[j]=a[0][j];
        for(i=1;i<=r;i++)
            v[j]-=a[l[i]][j];
        s+=v[j];
    }
    sort(v+1,v+n+1);
    for(j=1;j<=c;j++)
        s-=v[j];
    return s;
}
void bkt(int k){
    if(k==r+1){
        int s=solve();
        if(s>maxi)
            maxi=s;
    }else{
        int i;
        for(i=l[k-1]+1;i<=n;i++){
            l[k]=i;
            bkt(k+1);
        }
    }
}
int main(){
    int i,j,aux;
    freopen("elimin.in","r",stdin);
    freopen("elimin.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&r,&c);
    if(n<=m)
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
    else{
        aux=n;
        n=m;
        m=aux;
        aux=r;
        r=c;
        c=aux;
        for(i=1;i<=m;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&a[j][i]);
    }
    for(j=1;j<=m;j++)
        for(i=1;i<=n;i++)
            a[0][j]+=a[i][j];
    bkt(1);
    printf("%d",maxi);
    return 0;
}