Masala D
Sehrli Kvadrat Yo'li (Hard Version)
Sizga 𝑁 × 𝑁 o‘lchamdagi matritsa berilgan. Siz (1,1) dan (𝑁,𝑁) gacha yetib borishingiz kerak, ammo yo‘l uzunligi aniq 2 × 𝑁 − 1 bo‘lishi kerak va yo‘ldagi sonlar maksimal EKUK ga ega bo‘lishi lozim.
Bunda faqat quyidagi 3 yo‘nalishda harakatlanish mumkin:
- Pastga (↓)
- O‘ngga (→)
- Diagonali pastga-o‘ngga (↘️)
Siz shunday yo‘lni tanlashingiz kerakki, yo‘ldagi sonlarning EKUK qiymati maksimal bo‘lsin.
Kiruvchi ma'lumotlar:
Birinchi qatorda bitta butun son N (2 ≤ 𝑁 ≤ 15) – matritsaning o‘lchami.
Keyingi N qatorning har biri N ta butun sonni o‘z ichiga oladi: Aᵢⱼ (1 ≤ Aᵢⱼ ≤ 1000).
Chiquvchi ma'lumotlar:
Minimal EKUK qiymatini chiqaring.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 8 12 6 10 15 9 14 21 35 |
840 |
Izoh:
Eng yaxshi yo‘llardan biri:
8 → 12 → 15 → 21 → 35
Bu yo‘lda EKUK(8, 12, 15, 21, 35) = 4200 bo‘ladi.
Telegram kanalimizga obuna bo'ling