المپدیا

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

ابزار کاربر

ابزار سایت


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

Disjoint Rectangles

به یک مستطیل ‎«مستطیل منظم»‎ می‌گوییم اگر این مستطیل بطور کامل درون ربع اول صفحه مختصات بیفتد (‎ربع اول صفحه مختصات، نقاطی را شامل می‌شود که هم ‎$x$‎ آنها و هم ‎$y$‎‌ آنها بزرگتر یا مساوی صفر باشد‎(‎ و حداقل یکی از اضلاع آن منطبق بر یکی از محور‌های مختصات باشد. در این مسئله به شما ‎$n$‎ مستطیل منظم وزن‌دار داده شده است و شما باید برنامه‌ای بنویسید که زیر مجموعه‌ای از این مستطیل‌ها را بیابد که مستطیل‌های درون آن دو به دو مجزا باشند و وزن آن بیشینه شود. دو مستطیل مجزا هستند اگر مساحت اشتراک آن‌ها برابر با صفر باشد (‎دقت کنید که مساحت یک نقطه یا خط برابر با صفر است)‎ و همچنین وزن یک مجموعه از مستطیل‌ها برابر با مجموع وزن مستطیل‌های آن می‌باشد.

ورودی

  • در سطر اول ورودی عدد صحیح ‎$n$‎ آمده است که نشان‌دهنده تعداد مستطیل‌ها می‌باشد.
  • در ‎$n$‎ سطر بعدی در هر سطر ‎$5$‎ عدد صحیح ‎$x_1$‎، ‎$x_2$‎، ‎$y_1$‎، ‎$y_2$‎ و ‎$w$‎ آمده است که مشخصات مستطیل ‎$i$‎ام را نشان می‌دهد. ‎$x_1$‎ و ‎$x_2$‎ به ترتیب نشان‌گر مختصه ‎$x$‎ ضلع‌های سمت چپ و سمت راست مستطیل می‌باشند. ‎$y_1$‎‌ و ‎$y_2$‎ هم به ترتیب نشان‌گر مختصه ‎$y$‎ ضلع‌های پایین و بالای مستطیل می‌باشند و ‎$w$‎ نیز وزن مستطیل می‌باشد.
  • ‎ $1 \leq n \leq 7000$‎.
  • ‎ $0 \leq w \leq 10^9$‎.
  • ‎ $0 \leq x_1 < x_2 \leq 10^9$‎و ‎$0 \leq y_1 < y_2 \leq 10^9$‎.
  • ضمانت می‌شود تمام مستطیل‌های ورودی مستطیل‌های منظم هستند.

خروجی

در تنها سطر خروجی وزنِ پر‌وزن‌ترین زیرمجموعه مجزا از مستطیل‌های داده شده را چاپ کنید‎.

زیرمسئله‌ها

  • زیرمساله‌ی اول (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 500$‎.
  • زیرمساله‌ی دوم (۳۰ نمره): در همه‌ی تست‌ها ‎$n\leq 2500$‎.
  • زیرمساله‌ی سوم (۴۰ نمره): در همه‌ی تست‌ها ‎$n\leq 7000$‎.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
0 10 2 5 3‎
2 4 0 4 4‎
5 6 0 10 2
6


ابزار صفحه