Fişierul intrare/ieşire:pixels.in, pixels.outSursăRMMS 2011 - Ziua 2
AutorCatalin-Stefan TiseanuAdăugată deandrei.12Andrei Parvu andrei.12
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pixels

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 Aij pe care o provoacă dacă este colorat în alb. În al doilea rând, pentru fiecare pixel ştiţi cantitatea de plăcere Bij 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 Cijk 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), Cij0 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i - 1, j) sunt coloraţi diferit, Cij1 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i, j + 1) sunt coloraţi diferit, Cij2 este costul care trebuie plătit dacă acel pixel şi pixelul de la coordonatele (i + 1, j) sunt coloraţi diferit, şi Cij3 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 C110 va fi întotdeauna 0. Cij0 şi Ci-1j2 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 Aij pentru toţi pixelii coloraţi în alb + suma Bij 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ă!

Date de intrare

Fişierul de intrare pixels.in conţine pe prima linie N, dimensiunea matricii. Apoi urmează N linii cu N valori pe fiecare din ele. Cea de-a j-a valoare de pe linia i reprezintă Aij. În acelaşi format urmează N linii cu N valori reprezentând Bij. La final sunt N * N linii cu câte 4 valori pe fiecare linie. Cea de-a (i - 1) * N + j - a linie din acest grup conţine Cij0 Cij1 Cij2 Cij3.

Date de ieşire

În fişierul de ieşire pixels.out trebuie să afişaţi o singură linie care reprezintă plăcerea maximă care poate fi obţinută.

Restricţii

  • 1 ≤ N ≤ 100
  • 1 ≤ Aij, Bij, Cijk ≤ 100
  • 10% din teste vor avea N = 4
  • 30% din teste vor acea N = 10

Exemplu

pixels.inpixels.out
2
1 10
2 2
10 1
3 3
0 1 1 0
0 0 1 1
1 53 0 0
1 0 0 53
24

Explicaţie

Plăcerea maximă se obţine colorând

Negru Alb
Negru Negru

Observaţi că pixelii (2, 1) şi (2, 2) au un cost foarte mare de a fi colorţi diferit, aşa că îi veţi colora le fel, negru fiind opţiunea cea mai bună.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content