Antisense

Time limit: 0.3s Memory limit: 64MB Input: Output:

Cerință

Se dau două șiruri, AA și BB, a câte NN numere fiecare, indexate de la 11. Să se găsească valoarea maximă a expresiei (Al+Al+1+...+Ar)(Bl+Bl+1+...+Br)(A_{l}+A_{l+1}+...+A_{r}) - (B_{l}+B_{l+1}+...+B_{r}), cu 1lrN1 \leq l \leq r \leq N.

Date de intrare

Pe prima linie se găsește numărul natural NN. Pe a doua linie se găsesc, în ordine, cele NN elemente ale șirului AA. Pe a treia linie se găsesc, în ordine, cele NN elemente ale șirului BB.

Date de ieșire

Se va afișa un singur număr, reprezentând valoarea maximă a expresiei de mai sus.

Restricții și precizări

  • 1N200 0001 \leq N \leq 200 \ 000;
  • 109Ai,Bi109,i{1,2,,N}-10^9 \leq A_{i}, B_{i} \leq 10^9, \forall i \in \{1, 2, \dots, N\};
  • Pentru teste în valoare de 2626 de puncte, 1N1001 \leq N \leq 100;
  • Pentru teste în valoare de alte 2727 de puncte, 1N2 0001 \leq N \leq 2 \ 000;
  • Pentru restul de 4747 de puncte nu există restricții suplimentare.

Exemplu

stdin

5
7 6 10 6 -1
10 -1 22 0 -4

stdout

9

Explicație

Vom alege l=4l=4 și r=5r=5 și obținem (6+(1))(0+(4))=5(4)=9(6 + (−1)) − (0 + (−4)) = 5 - (-4) = 9. Această valoare este maximă.

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