المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲۳:سوال ۹

Walls

در زمین بایر پشت ده ما ‎$n$‎ دیوار ساخته‌اند که هیچکدام رنگ نشده‌است. هریک از دیوارها شامل ‎$m$‎ بلوک است. کدخدا تصمیم گرفته دیوارها را رنگ کند. او می‌خواهد بلوک ‎$j$‎ام از دیوار ‎$i$‎ام به رنگ ‎$a_{ij}$‎ درآید. نقاش ده در هر روز می‌تواند قلم خود را با رنگی دلخواه رنگی کرده و تعدادی بلوک متوالی از یک دیوار را رنگ کند. هم‌چنین هیچ ‌یک از بلوک‌ها نباید بیش از یک بار رنگ شوند. با توجه به این که کدخدا ‎$k$‎ روز دیگر برای بازدید از دیوارها می‌آید، ممکن است وقت کافی برای رنگ کردن همه‌ی بلوک‌ها به دلخواه کدخدا نباشد. پس نقاش ده می‌خواهد کاری کند که بیشترین تعداد بلوک‌ها به دلخواه کدخدا رنگ شوند. به او کمک کنید که این تعداد را به دست آورد.‎

ورودی

  • در سطر اول ورودی به ترتیب سه عدد ‎$n$‎، ‎$m$‎ و ‎$K$‎ آمده‌ است.
  • در ‎$n$‎ سطر بعد در هر سطر ‎$m$‎ عدد آمده است، که عدد ‎$i$‌‎ام در سطر ‎$j$‎ام برابر ‎$a_{ij}$‎‌ می‌باشد.
  • $1 \leq n,m,K \leq 600$‎.
  • $1 \leq a_{ij} \leq 10^9$‎.

خروجی

در تنها سطر خروجی ‎$K$‎ عدد چاپ کنید که عدد ‎$i$‎ام برابر جواب مساله به ازای ‎$k = i$‎ است. با تشکر‎!‎

زیرمسئله‌ها

  • زیرمسئله‌ی اول (۲۰ نمره): در همه‌ی تست‌ها ‎$n,m,K\leq 80$‎.
  • زیرمسئله‌ی دوم (۲۰ نمره): در همه‌ی تست‌ها ‎$n,m\leq 100$‎.
  • زیرمسئله‌ی سوم (۶۰ نمره): در همه‌ی تست‌ها ‎$n,m\leq 600$‎.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3 3 9
1 2 1‎
‎2 1 2‎
‎1 2 1
2 4 6 6 7 7 8 8 9‎
1 8 8
2 2 1 2 3 2 2 3‎
5 6 6 7 7 8 8 8‎

ابزار صفحه