АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Колумбын Кибдо бол дэлхийн хамгийн их хур бороо ордог хотуудын нэг юм.

Бүхэл жилийн турш энэ хотыг үүл бүрхэж байдаг. Энэ хот нь нэг хэмжээст шугам дээр байрладаг олон тооны хотхонуудтай.

Тоон шулуун дээрх хотхон тус бүрийн байрлал, хүн амыг та бүхэн сайн мэднэ. Үүлнүүд хотхонуудын дээр тодорхой зайд байрладаг.

Хэрэв хотхоны аль нэг хэсэгт ямар нэг үүлний сүүдэр тусаж байвал уг хотхоныг харанхуй гэе. Эсрэг тохиолдолд тус хотхоныг нартай гэе.

Хотын захиргаа хамгийн сүүлийн үеийн технологийг ашиглан яг нэг үүлийг зайлуулахад шаардлагатай мөнгөтэй байгааг тогтоов.

Ингэснээр тэд нэг үүлийг зайлуулсны дараа хамгийн цөөн тооны хүмүүсийг харанхуйд үлдээхийг хүсэв.

Яг нэг үүлийг зайлуулсны дараа нарлаг хотод амьдардаг хүмүүсийн хамгийн их тоо хэд байх вэ?

Тайлбар: 

Хэрэв ямар нэгэн хот ямар ч үүлээр бүрхэгдэхгүй бол аль хэдийн нартай гэж тооцогдсон тул эцсийн хариултад энэ хотхоны хүн амыг оруулах ёстой.

maximumPeople функц нь 4 ширхэг массив аргументтай ба эхний аргумент нь хотхон бүрийн хүн ам, хоёр дах нь хотхон бүрийн байршил,

3 дахь нь үүлний байршил, сүүлийнх нь үүлний бүрхэлтийн хэмжээний утгуудыг илэрхийлнэ.

Энэ функцийн буцаах утга нь яг нэг үүл хассаны дараа нарлаг хотод байх хүмүүсийн хамгийн их тоог буцаадаг бол тус функцийг гүйцээн бичнэ үү.

Оролт

Эхний мөрөнд ганц бүхэл тоо n байна. Энэ нь хотхонуудын тоо юм.

Дараагийн мөрөнд n бүхэл тоо p_i-үүд зайгаар тусгаарлагдан өгөгдөнө. i-р бүхэл тоо нь i-р хотхоны хүн амыг илэрхийлнэ.

Дараагийн мөрөнд  n бүхэл тоо x_i-үүд зайгаар тусгаарлагдан өгөгдөнө. i-р бүхэл тоо нь i-р хотхоны байршлыг илэрхийлнэ.

Дараагийн мөрөнд хотыг бүрхсэн үүлний тоог илэрхийлэх ганц бүхэл тоо m байна.

Дараагийн мөрөнд координатын тэнхлэг дээр i-р үүлний байршлыг илэрхийлэх y_i тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн мөрөнд үүлний зурвасыг заах бүхэл тоо r_i тоонууд зайгаар тусгаарлагдан өгөгдөнө.

Тайлбар : Үүл бүрийн хэмжээ нь байршлаасаа хамаарч тооцогддог, тухайлбал i-р үүл y_i байрлалд байрладаг бөгөөд хотхоноос r_i хол зайд оршдог.

Өөрөөр хэлбэл, i-р үүл нь | y_i - r_i , y_i + r_i | -р байршил бүр дэх хотхон бүрийг сүүдэрлэнэ.

Зааглалт

1 <= n <= 2 * 10^5

1 <= m <= 10^5

1 <= xi, yi, ri, pi <= 10^9.

Гаралт

Нэг үүлийг зайлуулснаар нарлаг хотод амьдардаг хүмүүсийн хамгийн их тоог илэрхийлэх ганц бүхэл тоо гарна.

Жишээ Оролт 0

2

10 100

5 100

1

4

1

Жишээ Гаралт 0

110

Тайлбар 0

Жишээнд эхний хотыг бүрхсэн ганц үүл байна. Бидний цорын ганц сонголт хотыг нартай болгох цорын ганц үүлийг арилгах явдал юм.

Ингэснээр бүх 110 хүн нарлаг хотод амьдрах болно.

Таны харж байгаачлан цорын ганц үүл нь 4 дээр байрлах ба r = 1 тул энэ үүл 3, 4, 5 дээр байрладаг хотуудыг бүрхэнэ.

Тиймээс эхний хотхон нь үүлээр бүрхэгдсэн бөгөөд энэ үүлийг зайлуулахад хот бүхэлдээ нартай болно.

Орчуулсан : Р.Мижиддорж МУБИС, доктор