F. Toshbaqa va tangalar
2000 ball
Toshbaqa n × m o‘lchamli maydonning yuqori chap katagida (1, 1) turibdi, uning uyi esa pastki o‘ng katakda (n, m). Toshbaqa sekin, lekin aqlli: u har qadamda faqat o‘ngga yoki pastga bitta katak yuradi.
Har bir katakda yo aᵢ,ⱼ ta tanga yotibdi, yo katta tosh bor (aᵢ,ⱼ = −1). Toshli katakka kirib bo‘lmaydi. Toshbaqa yo‘lida bosib o‘tgan barcha kataklardagi (boshlang‘ich va oxirgi katak ham) tangalarni yig‘ib oladi. U uyiga eng ko‘pi bilan nechta tanga olib borishi mumkin?
Kirish ma’lumotlari
Birinchi qatorda n va m.
Keyingi n ta qatorning har birida m ta butun son — aᵢ,ⱼ.
Chiqish ma’lumotlari
Bitta son — yig‘ish mumkin bo‘lgan tangalarning eng ko‘p soni. Agar toshbaqa uyiga umuman yetib bora olmasa, -1 chiqaring.
Cheklovlar
1 ≤ n, m ≤ 300; aᵢ,ⱼ = −1 yoki 0 ≤ aᵢ,ⱼ ≤ 10⁴; (1, 1) va (n, m) kataklarda tosh yo‘q.
| Testlar | Ball | Qo‘shimcha cheklovlar |
|---|---|---|
| 1–40 | 40 | n, m ≤ 7 |
| 41–70 | 30 | n, m ≤ 100 |
| 71–80 | 30 | to‘liq cheklovlar |
1–70-testlar 1 balldan, 71–80-testlar 3 balldan, jami 100 ball. 1–2-testlar — shartdagi misollar.
Misollar
3 4 1 3 -1 2 2 -1 5 1 4 1 2 3
13
2 2 0 -1 -1 5
-1
Tushuntirish
1-misol: 1 → 2 → 4 → 1 → 2 → 3 yo‘li 13 ta tanga beradi (rasmga qarang); bundan yaxshisi yo‘q. Masalan, 1 → 3 yo‘lini tanlasak, keyin o‘ngda ham, pastda ham tosh — toshbaqa qamalib qoladi.
2-misol: (1, 2) va (2, 1) kataklarda tosh bor — toshbaqa joyidan jila olmaydi, javob -1.