Masala #K6HJX6FEOQ
Alternating Pattern
\(n \times m\) o‘lchamli panjara berilgan. Har bir katakda \(0\) yoki \(1\) qiymat yozilgan.
Bir to‘rtburchak hudud alternate pattern deb ataladi, agar undagi har bir qo‘shni kataklar (yuqoriga, pastga, chapga yoki o‘ngga qarab) turli qiymatga ega bo‘lsa.
Boshqacha aytganda, bu hudud shaxmat taxtasiga o‘xshash bo‘lishi kerak.
Berilgan panjaradan shunday alternate pattern hududni topingki, uning yuzi maksimal bo‘lsin.
Hudud yuzi — undagi kataklar soni.
Kiruvchi ma'lumotlar:
- Birinchi qatorda \(n\) va \(m\) \((1\le n, m \le 2000)\)
- Keyingi \(n\) qatorda har birida \(m\) ta \(0\) yoki \(1\)
Chiquvchi ma'lumotlar:
Maksimal mumkin bo‘lgan yuzani chiqaring.
Subtasklar
- \(n, m \le 20\) (11 ball)
- \(n, m \le 70\) (13 ball)
- \(n, m \le 300\) (30 ball)
- Qo'shimcha cheklovlarsiz. (46 ball)
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 4 0 1 0 0 1 0 1 0 0 1 0 1 |
9 |
| 2 |
1 1 0 |
1 |
Izoh:
Agar yechimingiz Pythonda bo'lsa uni PyPyda jo'natish maslahat beriladi.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling