== include(page="template/taskheader" task_id="pion") ==
Poveste și cerință...
*Notă:* Această problemă este o versiune mai grea a problemei "pion":http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=1232 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.
h2. Date de intrare
Fișierul de intrare $pion.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $pion.out$ ...
Î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.
h2. 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.
h2. Exemplu
table(example).
|_. pion.in |_. pion.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3 4
3 7 8 5
4 9 6
| 8
DJDJJ
|
h3. 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.
== include(page="template/taskfooter" task_id="pion") ==
