Fişierul intrare/ieşire:temple.in, temple.outSursăInfoarena Monthly 2014, Runda 8
AutorAndrei HeidelbacherAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Temple

Tassadar vrea să exploreze un templu Xel’Naga, dar pentru a putea intra, trebuie să introducă un cod secret. În urma unor calcule matematice, a făcut câteva observaţii cu ajutorul cărora poate descoperi codul secret.
Fie o constantă K şi un şir V de N numere întregi. Fiecare poziţie i din şir are asociat un cost Ci. Definim Nexti = max(i, min(j | i < j, Vi < Vj)), iar NextiP = NextNextiP – 1.
Fie şirul S de N numere întregi, Si = max(Ci, CNexti, CNexti2, ..., CNextiK - 1). Codul secret este chiar şirul S!
Tassadar a reuşit să pătrundă în templul Xel’Naga. Voi puteţi?

Date de intrare

Fişierul de intrare temple.in conţine pe prima linie două numere întregi N şi K cu semnificaţia din enunţ. Pe a doua linie se află N numere întregi Vi reprezentând şirul V. Linia următoare conţine N numere întregi Ci reprezentând costurile poziţiilor din şirul V.

Date de ieşire

În fişierul de ieşire temple.out veţi afişa pe prima linie N numere întregi Si reprezentând codul secret.

Restricţii

  • 1 ≤ K ≤ N ≤ 105
  • -109 ≤ Vi ≤ 109
  • -1015 ≤ Ci ≤ 1015

Exemplu

temple.intemple.out
4 2
2 3 1 4
5 6 1 2
6 6 2 2

Explicaţie

Şirul Next este {2, 4, 4, 4}, iar şirul S este {max(5, 6), max(6, 2), max(1, 2), max(2)} = {6, 6, 2, 2}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content