Fișierul intrare/ieșire	bemo.in, bemo.out	Sursă	ad-hoc
Autor	Marius Stroe	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.15 sec	Limită de memorie	12288 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Bemo (clasele 11-12)

Notă: aceasta este o clonă a problemei Bemo de la ONI 2013 (Infoarena, Campion) cu limite mai stricte.

Notă: veți avea (probabil) nevoie să parsați intrarea, căci ultimele trei teste au fișiere de intrare de 16 – 17 MB.

Se dă o matrice cu R linii și C coloane de numere distincte de la 1 la R×C . Bemo, personajul emoțional, dorește să urmărească cel mai bun drum din colțul superior stânga, de coordonate (1, 1), în colțul inferior dreapta, de coordonate (R, C).

Un drum este o secvență de numere din matrice în care fiecare număr se găsește în jos sau la dreapta numărului anterior, i.e. dacă (i, j) este poziția unui număr de pe un drum, atunci următorul număr poate fi cel de pe poziția (i+1, j) sau cel de pe poziția (i, j+1). Pentru a determina dacă un drum A este mai bun decât un drum B, numerele fiecărui drum se vor sorta și se va alege cel mai mic lexicografic, e.g. [1,3,5,6,8] < [1,4,5,6,7].

Date de intrare

Fișierul de intrare bemo.in conține pe prima linie două numere naturale R și C, unde R este numărul liniilor, iar C numărul coloanelor matricei lui Bemo. Pe următoarele R linii se vor găsi câte C numere separate printr-un spațiu. Fiecare număr va fi unic și va fi cuprins în intervalul [1, R×C].

Date de ieșire

Fișierul de ieșire bemo.out va conține R+C-1 numere reprezentând cel mai bun drum pe care Bemo îl poate alege. Numerele vor fi scrise separate printr-un spațiu.

Restricții

• 0 < R, C < 1.501;
• Pentru 40% din teste: 0 < R, C < 751;
• Pentru 70% din teste: 0 < R, C < 1.301;
• Spunem că un drum A = (a₁, a₂, ..., a_R+C-1) este mai mic lexicografic decât un drum B = (b₁, b₂, ..., b_R+C-1) dacă există o poziție p astfel încât x_p < y_p și x₁ = y₁, x₂ = y₂, ..., x_p-1 = y_p-1.

Exemplu