Vi se dă o matrice de $N * N$ pixeli. Datoria voastră este să coloraţi fiecare pixel în alb sau negru astfel încât plăcerea vizuală să fie cât mai mare. Pentru a face asta trebuie să ştiţi 3 reguli. În primul rând, pentru fiecare pixel ştiţi cantitatea de plăcere $A{~ij~}$ pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere $B{~ij~}$ pe care o provoacă dacă este colorat în negru. În al treilea rând, ştiţi pentru fiecare pereche de pixeli adiacenţi (adică au o muchie în comun) care este costul plăcerii $C{~ijk~}$ care trebuie plătit dacă sunt coloraţi diferit.
Costul plăcerii este dat pentru fiecare pixel şi pentru fiecare 4 direcţii. Cu alte cuvinte, pentru un anumit pixel la coordonate $(i, j)$, $C{~ij0~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i - 1, j)$ sunt coloraţi diferit, $C{~ij1~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j + 1)$ sunt coloraţi diferit, $C{~ij2~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i + 1, j)$ sunt coloraţi diferit, şi $C{~ij3~}$ este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele $(i, j - 1)$ sunt coloraţi diferit.
Dacă un pixel nu are un vecin valid (adică unul care să facă parte din matrice), costul tot va fi dat, dar va fi 0. De exemplu $C{~110~}$ va fi întotdeauna 0. $C{~ij0~}$ şi $C{~(i-1)j2~}$ vor fi întotdeauna la fel, şi aşa mai departe (costul pentru fiecare pereche este simetric).

Voi trebuie să maximizaţi plăcerea totală, adică: * suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.

Voi trebuie să maximizaţi plăcerea totală, adică: *suma $A{~ij~}$ pentru toţi pixelii coloraţi în alb + suma $B{~ij~}$ pentru toţi pixelii coloraţi în negru - suma costurilor pixelilor adiacenţi coloraţi diferit*. Fiecare pereche de pixeli adiacenţi coloraţi diferit contribuie o singura dată (nu de două ori) la costul total pentru pixelii adiacenţi coloraţi diferit.

Baftă!
h2. Date de intrare