Masala C
Sehrli Kvadrat Yo'li
Sizga 𝑁 × 𝑁 o'lchamdagi butun sonlardan iborat matritsa berilgan. Siz matritsaning chap yuqori (1,1) burchagidan boshlaysiz va o'ng pastki (𝑁,𝑁) burchagiga borishingiz kerak. Ammo quyidagi shartlarga amal qilishingiz kerak:
- Faqat pastga yoki o'ngga harakat qilish mumkin (orqaga yoki chapga qaytib bo‘lmaydi).
- Harakatlanayotgan yo'lingizdagi sonlarning EKUB qiymati eng katta bo'lishi kerak.
- Yo'l oxirida olgan eng katta EKUB qiymatining o'zi javob bo'ladi.
Kiruvchi ma'lumotlar:
Birinchi qatorda bitta butun son N (2 ≤ 𝑁 ≤ 10) – matritsaning o'lchami.
Keyingi N qatorning har biri N ta butun sondan iborat bo‘lib, Aᵢⱼ (1 ≤ Aᵢⱼ ≤ 1000) qiymatlar bilan berilgan.
Chiquvchi ma'lumotlar:
Berilgan shartlarga mos keladigan eng katta EKUB ni chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 6 12 4 8 18 9 10 30 15 |
6 |
Izoh:
Siz eng katta EKUB bo'ladigan yo'lni tanlashingiz kerak:
6 → 12 → 18 → 30
Bu yo'lda EKUB(6, 12, 18, 30) = 6 bo‘ladi.
Telegram kanalimizga obuna bo'ling