Fişierul intrare/ieşire:pion.in, pion.outSursăcampion
AutorNistor-Eugen MotAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Pion

Notă: Această problemă este o versiune mai grea a problemei pion de pe Campion.

Două persoane au inventat un joc cu următoarele reguli:

  1. Spaţiul de joc este o matrice cu m + 1 linii şi n + 1 coloane. Numerotarea liniilor şi a coloanelor se face începând de la 1. Linia m + 1 şi coloana n + 1 conţin numere întregi strict pozitive.
  2. În poziţia (1,1) se găseşte un pion pe care jucătorii îl deplasează alternativ într-o poziţie învecinată. Sunt permise doar deplasări din poziţia ($i$, j) în poziţia ($i$ + 1, j) sau ($i$, j + 1) cu condiţia i ≤ m şi j ≤ n (deci pionul ajuns pe ultima linie sau ultima coloană nu se mai deplasează).
  3. În momentul când pionul nu se mai poate deplasa, jucătorul care a făcut prima mutare primeşte de la celălalt o sumă de bani egală cu numărul de pe poziţia în care a ajuns.

Determinaţi suma de bani maximă pe care o poate câştiga jucătorul care începe jocul, precum şi traseul urmat de pion, ştiind că ambii jucători joacă optim.

Date de intrare

Fişierul de intrare pion.in conţine pe prima linie numerele m şi n, pe linia a doua n numere întregi, reprezentând valorile de pe linia m + 1 coloanele 1 ... n, iar pe linia a treia m numere reprezentând valorile de pe coloana n + 1, liniile 1 ... m. Pe poziţia ($m$ + 1, n + 1) putem considera că se află numărul 0, poziţia fiind inaccesibilă, în condiţiile jocului.

Date de ieşire

În fişierul de ieşire pion.out se va scrie, pe prima linie, un număr reprezentând câştigul maxim al primului jucător. Pe a doua linie se va scrie un şir de litere „J” şi „D” indicând mutările (în jos sau la dreapta) urmate de pion.

Restricţii

  • 1 ≤ m, n ≤ 5.000
  • Numerele de pe ultima linie şi coloană sunt întregi din intervalul [1, 60.000].
  • Dacă la orice moment ambele mutări duc la acelaşi scor optim, jucătorii vor prefera mutarea în jos.

Exemplu

pion.inpion.out
3 4
3 7 8 5
4 9 6
8
DJDJJ

Explicaţie

Jucătorul 1 mută pionul în căsuţa (1, 2). Jucătorul 2 mută pionul în căsuţa (2, 2). Jucătorul 1 mută pionul în căsuţa (2, 3). Jucătorul 2 mută pionul în căsuţa (3, 3). Jucătorul 1 mută pionul în căsuţa (4, 3).

Dacă jucătorul 1 ar începe jocul mutând la (2, 1), atunci jucătorul 2 ar răspunde mutând la (3, 1). De aici, jucătorul 1 n-ar putea obţine decât scorul 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici