D. Гүйцэд графын бодлого

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

"Гүйцэд графын бодлого" нь хамгийн алдартай NP-гүйцэд бодлогуудын нэг юм. Зарим хялбарчлах үйлдэл хийсний дараа бодлого маань дараахь байдалд ордог байна. Чиглэлгүй $G$ граф авч үзье. Дурын хоёр орой нь $G$-ийн ирмэгээр холбогдсон байх хамгийн том хэмжээтэй $G$-ийн оройнуудын олонлог $C$-г ол. Тун энгийн байгаа биз. Хэн ч энэхүү бодлогын графын оройн тооны хувьд олон гишүүнтийн хугацаанд олох алгоритм олж чадаагүй л байгаа. Гэсэн хэдий ч бусад олон NP-гүйцэд бодлогуудын адилаар "Гүйцэд графын бодлого" нь тодорхой графуудын хувьд хялбархан бодогддог байна.

Шулууны дагуу $n$ ялгаатай цэг авч үзье. $i$ дэх цэг нь $x_{i}$ координат болон $w_{i}$ жинтэй гэж үзье. $G$ нь уг цэгүүдээр оройнуудаа хийсэн, $(i, j)$ оройнууд хоорондох зай нь жингүүдийн нийлбэрээс багагүй үед буюу $|x_{i} - x_{j}| ≥ w_{i} + w_{j}$ үед ирмэгээр холбогдсон байх граф гэж үзье.

Уг графын гүйцэд дэд графын оройн боломжит хамгийн их утгыг ол.

Оролт

Эхний мөрөнд цэгүүдийн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 200 000$) гэсэн бүхэл тоо байна.

Дараагийн $n$ мөр бүрт $i$ дэх цэгийн координат болон жинг илэрхийлэх $x_{i}$, $w_{i}$ ($0 ≤ x_{i} ≤ 10^{9}, 1 ≤ w_{i} ≤ 10^{9}$) тоонууд байна. $x_{i}$ нар хоорондоо ялгаатай.

Гаралт

Графын гүйцэд дэд графын оройн боломжит хамгийн их утгыг хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
4
2 3
3 1
6 1
0 2
Гаралт
3

Тэмдэглэл

Хэрэв чи энэхүү бодлогыг дээрх нөхцөлүүдгүйгээр бодох арга олбол чи сая долларын эзэн болох боломжтой!

Жишээг зургаар илэрхийлбэл.

Сэтгэгдлүүдийг ачааллаж байна...