E. Дайралт хийх үү эсвэл үгүй юу

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

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

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

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

Динамик онооны системтэй гурван бодлогоос тогтох энгийн Кодфорсесийн раундыг авч үзье.

Танд эцсийн онооны самбар бараг бүхлээрээ өгөгдсөн. Бүх оролцогчдын хувьд (таныг оролцуулаад) бодлого бүрийн зөвшөөрөгдсөн бодолтуудын хугацаа өгөгдсөн. Мөн шийдэл бүрийн хувьд та аль хэдийн энэ шийдэлрүү дайралт хийх боломжтой эсэхийг мэдэж байгаа. Раунд дуусахаас өмнө болж болох онооны самбар дээрх өөрчлөлтүүд нь таны боломж юм.

Төгсгөлд нь таны эзлэж болох хамгийн сайн байр юу вэ?

Өөрөөр $n$ хүмүүс (таныг оролцуулаад) оролцож байна. Дурын бодлогын хувьд энэ бодлогогыг раундын төгсгөлд $k$ хүн бодсон байвал энэ бодлогын хамгийн их оноо нь:

  1. Хэрвээ $n < 2k ≤ 2n$ байвал хамгийн их оноо нь $500$;
  2. Хэрвээ $n < 4k ≤ 2n$ байвал хамгийн их оноо нь $1000$;
  3. Хэрвээ $n < 8k ≤ 2n$ байвал хамгийн их оноо нь $1500$;
  4. Хэрвээ $n < 16k ≤ 2n$ байвал хамгийн их оноо нь $2000$;
  5. Хэрвээ $n < 32k ≤ 2n$ байвал хамгийн их оноо нь $2500$;
  6. Хэрвээ $32k ≤ n$ байвал хамгийн их оноо нь $3000$ гэж тодорхойлогдоно.

Нэг бодлогын боломжит хамгийн их оноог $s$ гэе. Тэгээд энэ бодлогыг бодоод зөвшөөрүүлж чадаагүй (эсвэл түүний шийдэл дайралтад өртсөн) оролцогч энэ бодлогын хувьд $0$ оноо авна. Хэрвээ тэр тэмцээн эхэлснээс хойш $t$ минутанд шийдлээ зөвшөөрүүлж чадах юм бол (мөн түүний шийдэл дайралтад өртөөгүй) тэр уг бодлогын хувьд оноо авна.

Оролцогчийн нийт оноо нь бодлого бүрээс цуглуулсан оноонуудын нийлбэр ба үүн дээрээ амжилттай дайралт болгоныхоо хувьд $100$ оноо цуглуулна (зөвхөн та халдлага хийнэ).

Таны эзлэх байр таниас илэрхий их нийт оноотой оролцогчдын тоон дээр нэгийг нэмсэнтэй тэнцүү байна.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 5000$) байх буюу оролцогчдын тоо байна. Та $1$ дугаартай оролцогч байна.

Дараагийн $n$ мөр бүрт гурван бүхэл тоон утга $a_{i}$, $b_{i}$ ба $c_{i}$ байна. Энд $a_{i} = 0$ гэдэг нь $i$-р оролцогч эхний бодлогыг шийдэж чадаагүй гэсэн үг. Хэрвээ $1 ≤ a_{i} ≤ 120$ байвал $i$-р оролцогч эхний бодлогыг тэмцээн эхэлснээс $a_{i}$ минутын дараа шийдсэн ба та энэ шийдэлд дайралт хийж чадахгүй. Харин $ - 120 ≤ a_{i} ≤  - 1$ байвал $i$-р оролцогч эхний бодлогыг тэмцээн эхэлснээс хойш $ - a_{i}$ минутын дараа шийдсэн ба та энэ шийдэлд дайралт хийж болно. Үүнтэй адилаар $b_{i}$ ба $c_{i}$ нь гурав болон дөрөвдүгээр бодлогуудын мэдээллийг ижил форматтайгаар хангана.

$a_{1}$, $b_{1}$ ба $c_{1}$ бүхэл тоонууд нь эерэг байна.

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
4
120 120 1
61 61 120
-61 61 120
0 0 0
Гаралт
1
Оролт
4
0 0 119
-3 -17 -42
0 7 0
51 0 0
Гаралт
2

Тэмдэглэл

Эхний жишээг авч үзье. Хэрвээ та ямар ч шийдэлд дайралт хийхгүй бол та тэмцээнд ялна (зүүн талын онооны самбар). Гэсэн ч хэрвээ та гурав дахь оролцогчийн эхний бодлогын шийдэлд дайралт хийвэл (таны дайралт хийж чадах ганц шийдэл нь) таны эхний бодлогын боломжит хамгийн их оноо өөрчлөгдөх ба та хоёрдугаар байрыг эзлэнэ (баруун талын онооны самбар).

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