abrupt

Time limit: 0.2s Memory limit: 64MB Input: abrupt.in Output: abrupt.out

Cerință

Se dau două șiruri AA și BB, ambele cu câte nn elemente, ordonate crescător. Se mai dă un număr mm. Dorim să construim un șir CC cu mm elemente cu următoarele proprietăți:

  • să fie crescător;
  • să existe o valoare pp (1p<m1 \leq p \lt m), astfel încât primele pp elemente din CC să formeze secvență în AA, iar ultimele mpm-p elemente din CC să formeze o secvență din BB;
  • considerând DD șirul cu cele m1m-1 diferențe a câte doi termeni consecutivi din CC (în valoare absolută), valoarea cea mai mare din DD să fie maxim posibilă.

Date de intrare

Fișierul abrupt.in conține pe prima linie numerele nn și mm, separate prin spațiu. Pe linia a doua se află nn numere naturale, în ordine crescătoare, separate prin spațiu, reprezentând elementele șirului AA. Pe linia a treia se află nn numere naturale, în ordine crescătoare, separate prin spațiu, reprezentând elementele șirului BB.

Date de ieșire

Fișierul abrupt.out va conține un singur număr natural reprezentând valoarea maximă din șirul DD.

Restricții și precizări

  • 1n300 0001 \leq n \leq 300 \ 000;
  • 2m2×n2 \leq m \leq 2 \times n;
  • Elementele șirurilor AA și BB sunt naturale cel mult egale cu 2 000 000 0002 \ 000 \ 000 \ 000;
  • Pentru 2020 de puncte, n50n \leq 50;
  • Pentru 4040 de puncte, n200n \leq 200;
  • Pentru 6060 de puncte, n2 000n \leq 2 \ 000;

Exemplu

abrupt.in

3 4
2 6 7
3 8 9

abrupt.out

5

Explicație

Putem forma șirul CC astfel: 2 3 8 92 \ 3 \ 8 \ 9. Șirul DD ar avea valorile 1 5 11 \ 5 \ 1.

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