Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | fence.in, fence.out | Sursă | ONI 2015, clasa a 10-a |
| Autor | Pit-Rada Vasile | Adăugată de |  Puscas Sergiu •harababurel |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/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 ...
Date de ieşire
În fişierul de ieşire fence.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| fence.in | fence.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
