Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۱:عملی مقدماتی دوم:سوال ۲

Fat boys

در هر خانه‌ي يک جدول ‎m×n‎ يک نفر ايستاده است. مي‌خواهيم زير مستطيلي از اين جدول را انتخاب کنيم، به طوري که مجموع وزن افراد درون اين زيرمستطيل بيشينه شود و همچنين تعداد افرادي که وزن‌شان از مقدار ‎x‎ بيشتر است، از ‎k‎ بيشتر نشود.

ورودی

  • در سطر اول ورودی دو عدد ‎(1n,m400)‎ آمده است‎.‎
  • در خط دوم دو عدد طبيعي آمده است. عدد اول ‎x‎ و عدد دوم ‎(1kn×m)‎ را نشان مي‌دهد.
  • در ‎n‎ خط بعد، در هر خط ‎m‎ عدد طبيعي آمده است که وزن افراد را نشان مي‌دهد.
  • عدد ‎x‎ و وزن افراد عددي طبيعي است بین ‎1‎ و ‎1000000‎ می‌باشند.

خروجی

در خروجي تنها بايد يک عدد که بيشينه مجموع وزن افراد است، چاپ کنيد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2 3
5 1
10 3 7
3 5 9
17

ابزار صفحه