Simulare Lot 2018 Baraj 4 Juniori | panou

This was the problem page during the contest. Access the current page here.
Time limit: 0.4s Memory limit: 64MB Input: panou.in Output: panou.out

Gigel vrea să-şi deschidă o firmă de publicitate. Întrucât nu are experienţă, s-a decis să înceapă modest închiriind QQ panouri publicitare, din care la randul lui va închiria anumite porţiuni. Astfel el s-a decis să divizeze fiecare panou de înălţime HH într-un număr maxim posibil de regiuni/benzi orizontale, toate de înălţime hh, deci identice, cu condiţia să nu se suprapună. De asemenea, el a făcut o analiză a pieţei şi a asociat profitul PhP_h ce l-ar putea obţine pentru o regiune de înălţime hh, 1hhmax1 \leq h \leq h_{max}. Întrucât fiecare client are propria opinie despre dimensiunea reclamei perfecte, profiturile nu sunt corelate cu dimensiunile, astfel fiind posibil ca regiuni mai mici să genereze profit mai mare.

Cerinţa

Cunoscând secvenţa profiturilor, P1P_1, P2P_2, \dots, PhmaxP_{h_{max}}, Gigel îşi doreşte să afle pentru o listă de panouri H1H_1, H2H_2, \dots, HQH_Q care vor fi profiturile maxime asociate.

Date de intrare

Fişierul de intrare panou.in conţine pe prima linie hmaxh_{max} şi QQ, separate printr-un spaţiu. Pe linia a doua se se află hmaxh_{max} numere P1P_1, P2P_2, \dots, PhmaxP_{h_{max}} separate prin câte un spaţiu reprezentând profiturile. Pe linia a treia se dau, separate prin câte un spaţiu, înălţimile H1H_1, H2H_2, \dots, HQH_Q ale celor QQ panouri care se vor închiria

Date de ieșire

Fisierul de ieşire panou.out va conţine QQ linii, pe linia kk, 1kQ1 \leq k \leq Q, se va afla câte un număr reprezentând profitul maxim obţinut pentru al kk-lea panou.

Restricții și precizări

  • 1hmax100 0001 \leq hmax \leq 100 \ 000
  • 1Q10 0001 \leq Q \leq 10 \ 000
  • 1Pi100 0001 \leq P_i \leq 100 \ 000
  • 1Hi10 000 0001 \leq H_i \leq 10 \ 000 \ 000
  • Pentru 70%70\% din punctaj Hi100 000H_i \leq 100 \ 000
  • Pentru 10%10\% din punctaj hmax1 000h_{max} \leq 1 \ 000 şi Q1 000Q \leq 1 \ 000

Exemplu

panou.in

3 2
1 3 5
6 8

panou.out

10
12

Explicație

Pentru H=6H = 6 avem doua benzi de inaltime 33 obtinand castigul maxim 25=102 \cdot 5 = 10
Pentru H=8H = 8 avem 44 benzi de inaltime 22 obtinand castigul maxim 43=124 \cdot 3 = 12

Log in or sign up to be able to send submissions!