Cod sursa(job #1488537)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 19 septembrie 2015 10:12:58
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,i,j,a[16][1000],r,c,k,x,d,u,l[16],q[1000],s[33000],v;
int main() {
    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[j][i]);
        x=n,n=m,m=x,x=r,r=c,c=x;
    }
    else
        for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    if(r>1) {
        for(k=1;k<(1<<(n-1));k++) {
            s[k<<1]=s[k],v=0,s[(k<<1)+1]=s[k]+1;
            if(s[k]==r-1)
                v=k<<1;
            else if(s[k]==r-2)
                v=1+(k<<1);
            if(v) {
                for(i=1;v;v>>=1)
                    l[i++]=v&1;
                for(j=1;j<=m;j++)
                    q[j]=0;
                for(i=1,d=0;i<=n;i++)
                if(!l[i])
                    for(j=1;j<=m;j++)
                        q[j]+=a[i][j],d+=a[i][j];
                else
                    l[i]=0;
                sort(q+1,q+m+1);
                for(j=1;j<=c;j++)
                    d-=q[j];
                if(d>u)
                    u=d;
            }
        }
        if(s[k]==r-1)
            v=k<<1;
        if(v) {
            for(i=1;v;v>>=1)
                l[i++]=v&1;
            for(j=1;j<=m;j++)
                q[j]=0;
            for(i=1,d=0;i<=n;i++)
            if(!l[i])
                for(j=1;j<=m;j++)
                    q[j]+=a[i][j],d+=a[i][j];
            else
                l[i]=0;
            sort(q+1,q+m+1);
            for(j=1;j<=c;j++)
                d-=q[j];
            if(d>u)
                u=d;
        }
    }
    else if(r==1) {
        for(k=1;k<=n;k++) {
            for(j=1;j<=m;j++)
                q[j]=0;
            for(i=1,d=0;i<=n;i++)
            if(i!=k)
                for(j=1;j<=m;j++)
                    q[j]+=a[i][j],d+=a[i][j];
            sort(q+1,q+m+1);
            for(j=1;j<=c;j++)
                d-=q[j];
            if(d>u)
                u=d;
        }
    }
    else if(c) {
        for(i=1,u=0;i<=n;i++)
        for(j=1;j<=m;j++)
            q[j]+=a[i][j],u+=a[i][j];
        sort(q+1,q+m+1);
        for(j=1;j<=c;j++)
            u-=q[j];
    }
    printf("%d",u);
}