Arbitraža

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Tam s Triglava vije se zastava,
za nami je ognjeni krst.
Sladka je slovenska zmaga,
svoboden bo kmalu Trst.
― Agropop, Z nami je Slovenija

Slovenski politiki se pripravljajo na zagovor pred Evropsko komisijo, v katerem bodo odgovornim evropskim politikom zašpecali Hrvaško, ki se vede neprimerno. Razložili bodo, da se Sloveniji dogaja strašna krivica. Strokovnjaki so pripravili n pravnih in m političnih argumentov. Ker je zagovor časovno omejen, lahko vključijo največ k argumentov.

Vsak argument ima svojo moč, ki je naravno število. Moči pravnih argumentov označimo s p_1, \ldots, p_n, moči političnih argumentov pa s s_1, \ldots, s_m. Recimo, da smo za zagovor izbrali a pravnih argumentov z močmi p'_1, \ldots, p'_a in b političnih argumentov z močmi s'_1, \ldots, s'_b. Argumente p'_1, \ldots, p'_a poljubno izberemo izmed p_1, \ldots, p_n. Prav tako argumente s'_1, \ldots, s'_b poljubno izberemo izmed s_1, \ldots, s_m. Potem skupno moč zagovora, ki jo označimo z M, izračunamo takole:

  • Če velja a \geq b, potem je M=a\cdot(p'_1\cdot s'_1 + \cdots + p'_b\cdot s'_b+p'_{b+1}+\cdots + p'_a).
  • Če velja a < b, potem je M=b\cdot(p'_1\cdot s'_1 + \cdots + p'_a\cdot s'_a+s'_{a+1}+\cdots + s'_b).

Izbrana a in b morata seveda ustrezati pogojem a+b\leq k, 0\leq a\leq n in 0\leq b\leq m. Kolikšna je največja moč zagovora M, ki jo lahko dosežemo z optimalno izbiro argumentov in njihovega vrstnega reda?

Vhodni podatki

V prvi vrstici se nahajajo naravna števila n, m in k, ki so ločena s presledki. V drugi vrstici se nahaja n naravnih števil p_1, \ldots, p_n, ki so ločena s presledki. To so moči pravnih argumentov. V tretji vrstici se nahaja m naravnih števil s_1, \ldots, s_m, ki so ločena s presledki. To so moči političnih argumentov.

Omejitve vhodnih podatkov

  • 1 \leq n,m,k \leq 10^5
  • 1 \leq p_i \leq 10^5 za vse i = 1, \ldots, n
  • 1 \leq s_i \leq 10^5 za vse i = 1, \ldots, m

Izhodni podatki

Izpišite največjo možno moč zagovora, ki jo lahko dobimo z optimalno izbiro argumentov in njihovega vrstnega reda. Zagotovljeno je, da rezultat ne bo presegel 2^{63}-1.

Primer

Vhod

4 3 4
1 4 3 1
2 1 2

Izhod

36

Komentar

Moč 36 lahko dosežemo, če na primer vzamemo pravne argumente z močmi 4, 1 in 3 (v tem vrstnem redu) ter politični argument z močjo 2. Skupna moč je 3 \cdot (4 \cdot 2+1+3) = 36.

Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task