Fişierul intrare/ieşire:fence.in, fence.outSursăONI 2015, clasa a 10-a
AutorPit-Rada VasileAdăugată deharababurelPuscas Sergiu harababurel
Timp execuţie pe test0.4 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fence

Un proprietar vinde un teren de formă dreptunghiulară împărţit în M × N parcele de formă pătrată cu lungimea laturii de o unitate. Fiecare parcelă costă V lei. Vlad s-a interesat şi a aflat pentru fiecare din parcelele terenului care este valoarea de revânzare. El constată că unele parcele i-ar putea aduce profit, iar altele i-ar aduce pierdere. Fiind isteţ, negociază cu proprietarul să cumpere atâtea parcele de teren câte pot fi împrejmuite cu un singur gard de lungime egală cu 2M + 2N unităţi. Terenul are pe fiecare din cele patru laturi acces la drumul exterior, pe o porţiune de lungime egală cu o unitate. Vlad negociază astfel încât terenul achiziţionat să conţină şi cele patru parcele de acces la exterior.

Cerinţă

Cunoscând M şi N (dimensiunile terenului), V (preţul de cumpărare al fiecărei parcele), x_nord, x_sud, y_vest şi y_est (poziţiile parcelelor cu acces la drumul exterior) şi A[i][j], 1 ≤ i ≤ M şi 1 ≤ j ≤ N (valorile de revânzare pentru fiecare parcelă), să se determine:

  • Profitul P_arie_minimă pe care-l poate obţine Vlad după cumpărarea şi apoi revânzarea suprafeţei de teren de arie minimă, împrejmuită conform condiţiilor negociate.
  • Profitul maxim P_max pe care-l poate obţine Vlad după cumpărarea şi apoi revânzarea unei suprafeţe de teren împrejmuită conform condiţiilor negociate.

Date de intrare

Fişierul de intrare fence.in conţine pe prima linie numărul t. Pentru toate testele de intrare numărul t poate avea doar valoarea 1 sau valoarea 2.
Pe linia a doua se găsesc numerele M, N, V, x_nord, x_sud, y_vest şi y_est separate prin câte un spaţiu, iar pe următoarele M linii se află câte N numere naturale separate prin câte un spaţiu, reprezentând valorile de revânzare ale celor M × N parcele de teren.

Date de ieşire

Dacă valoarea lui t este 1, atunci se va rezolva numai primul punct din cerinţă.
În acest caz în fişierul de ieşire fence.out se va scrie pe prima linie numărul P_arie_minimă.

Dacă valoarea lui t este 2, atunci se va rezolva numai al doilea punct din cerinţă.
În acest caz în fişierul de ieşire fence.out se va scrie pe prima linie numărul P_max.

Restricţii

  • 3 ≤ M ≤ 1 000
  • 3 ≤ N ≤ 1 000
  • 1 000 ≤ V ≤ 10 000
  • 1 ≤ A[i][j] ≤ 20 000
  • 2 ≤ x_nord, x_sud ≤ N-1
  • 2 ≤ y_vest, y_est ≤ M-1
  • (x_nord - x_sud) × (y_est - y_vest) ≥ 0
  • Prin profit se înţelege suma valorilor de revânzare corespunzătoare parcelelor din suprafaţa împrejmuită din care se scade produsul dintre preţul de cumpărare V şi numărul parcelelor împrejmuite, care poate fi şi negativ.
  • Pentru rezolvarea corectă a primei cerinţe se va obţine 20% din punctaj.
  • Pentru 33% din testele corespunzătoare celei de-a doua cerinţe va fi îndeplinită condiţia M, N ≤ 15.

Exemplu

fence.infence.out
1
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2
3
2
5 7 6 3 5 3 2
3 5 8 4 9 8 7
9 3 7 6 4 5 9
6 6 8 2 5 4 8
3 3 4 7 7 2 1
8 7 9 2 8 4 2
8

Explicaţie

M=5, N=7, V=6, x_nord=3, x_sud=5, y_vest=3, y_est=2

  • În primul exemplu: P_arie_minimă = (8+7+6+4+5+9+6+6+8+2+5+7+8) - 6*13 = 81-78 = 3
  • În al doilea exemplu: P_max = (8+4+9+8+7+7+6+4+5+9+6+6+8+2+5+7+7+8) - 6*18 = 116-108 = 8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?