Cod sursa(job #2774937)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 13 septembrie 2021 17:05:12
Problema Elimin Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 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);
    return 0;
}