Cod sursa(job #542451)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 26 februarie 2011 13:43:27
Problema Pixels Scor 40
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 2 Marime 2.15 kb
#include<stdio.h>

#define maxim(a,b) (a>b ? a : b)
#define INF 2000000006
#define NMAX 105

int a[NMAX][NMAX],b[NMAX][NMAX],n;
int c[NMAX][NMAX][4],d[NMAX][2254];
int s[NMAX][NMAX];

int main ()
{
    int i,j,k,cj,ck,poz,sol=0,solm,r,rp;
    
    freopen("pixels.in","r",stdin);
    freopen("pixels.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&b[i][j]);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d%d%d%d",&c[i][j][0],&c[i][j][1],
                             &c[i][j][2],&c[i][j][3]);
    if(n<=10)
    {
        for(i=1;i<=n;i++)
            for(j=0;j<(1<<n);j++)
            {
                cj=j;rp=0;
                for(poz=1;poz<=n;poz++)
                {
                    r=(cj&1);
                    d[i][j]+=(r?b[poz][i]:a[poz][i]);
                    if(r!=rp)
                        d[i][j]-=c[poz][i][0];
                    rp=r;
                    cj=(cj>>1);
                }
                solm=-INF;
                for(k=0;k<(1<<n);k++)
                {
                    sol=0;
                    ck=(k^j);
                    for(poz=0;poz<n;poz++)
                        if(ck&(1<<poz))
                            sol-=c[poz+1][i][3];
                    solm=maxim(solm,sol+d[i-1][k]);
                }
                d[i][j]+=solm;
            }
        solm=-INF;
        for(i=0;i<(1<<n);i++)
            solm=maxim(solm,d[n][i]);
        printf("%d\n",solm);
        return 0;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(b[i][j]>a[i][j])
            {
                s[i][j]=1;
                sol+=b[i][j];
            }
            else
            {
                s[i][j]=-1;
                sol+=a[i][j];
            }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(s[i][j]!=s[i-1][j])
                sol-=c[i][j][0];
            if(s[i][j]!=s[i][j-1])
                sol-=c[i][j][3];
        }
    printf("%d\n",sol);
    return 0;
}