| Fişierul intrare/ieşire: | pion.in, pion.out | Sursă | campion |
| Autor | Nistor-Eugen Mot | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 1 sec | Limită de memorie | 2048 kbytes |
| Scorul tău | N/A | Dificultate |   3/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.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:
- 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.
- Î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ă).
- Î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.in | pion.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.
