Masala E
Kuryer yo'li
Shaharda yangi turdagi “aqlli” kuryer-robot sinovdan o‘tkazilmoqda. Shahar xaritasi to‘g‘ri to‘rtburchak shaklida bo‘lib, u \(N\) ta qator va \(M\) ta ustundan iborat. Har bir katak — bir blok (maydon) va u yerda signal darajasi yozilgan.
Qiziq tomoni: xaritadagi signal darajalari 1 dan \(N*M\) gacha bo‘lgan barcha sonlardan iborat.
Robotning harakati cheklangan:
- u har safar qo‘shni blokka 1 qadam bilan o‘tadi;
- faqat o‘ngga (Sharq) yoki pastga (Janub) yurishi mumkin.
Robot yo‘l (marshrut)ni istalgan blokdan boshlashi va istalgan blokda tugatishi mumkin (harakat qoidalariga rioya qilgan holda).
Robot ishlab chiqaruvchilari marshrutni “muvaffaqiyatli” deb baholashadi, agar:
- marshrut tugagan blokdagi signal darajasi boshlangan blokdagidan katta bo‘lsa.
Ya’ni marshrut “muvaffaqiyatli” bo‘lishi uchun, oxirgi signal birinchidan kuchliroq bo‘lishi shart.
Istalgan “muvaffaqiyatli” marshrut ichida robot bosib o‘tishi mumkin bo‘lgan bloklar sonining eng katta qiymati \(Z\) ni toping.
Birinchi qatorda \(N\) va \(M\) beriladi. \((1\le N, M\le 2000)\)
Keyingi \(N\) qatorda \(M\) tadan son — har bir blokdagi signal darajasi beriladi. \(1\le signal\le N * M\)
Matritsada 1 dan \(N*M\) gacha bo‘lgan barcha sonlar aynan bir martadan uchraydi.
Yagona qatorda masala javobi \(Z\) ni chiqaring.
Agar birorta ham muvaffaqiyatli marshrut mavjud bo‘lmasa, 0 ni chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 4 12 11 10 6 7 5 4 3 9 2 8 1 |
4 |
| 2 |
3 3 5 8 7 9 6 4 3 1 2 |
3 |
Telegram kanalimizga obuna bo'ling