F. Групп төслүүд

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

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

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

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

Ангид групп төслүүд дээр ажиллаж буй $n$ оюутнууд байна. Оюутнууд группуудэд (зарим оюутнууд ганцаараа групп байж болно) хуваагдах ба өөрсдийн бие даасан хэсэг дээр ажиллах ба үр дүнг хамтдаа хэлэлцэнэ. $i$-р оюутанд өөрийн хэсгийг дуусгахад $a_{i}$ минут шаардлагатай.

Хэрвээ оюутнууд өөр өөр хурдаар ажиллавал хурдан оюутнуудад залхмаар санагдах бол удаан оюутнуудад ачаалалтай байна. Тухайлбал группийн тэнцвэргүй байдал нь группт байгаа хамгийн их $a_{i}$-с хасах нь хамгийн бага $a_{i}$ гэж тодорхойлогдоно. Нэг оюутантай группийн тэнцвэргүй байдал нь $0$ байна. Бүх группийн нийт тэнцвэргүй байдал нь хамгийн ихдээ $k$ байхаар оюутнуудыг хэдэн янзаар хувааж болох вэ?

Нэг хуваалтанд ижил группт ажиллаж байгаа боловч өөр хуваалтанд өөр группт байгаа хос оюутан оршин байвал тус хоёр хуваалтыг ялгаатай гэж үзнэ.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 200$, $0 ≤ k ≤ 1000$) байх ба харгалзан оюутнуудын тоо ба нийт тэнцвэргүй байдлын байж болох хамгийн их утга юм.

Хоёр дахь мөрөнд $n$ ширхэг бүхэл тоон утга $a_{i}$ ($1 ≤ a_{i} ≤ 500$) байх ба $i$-р оюутны өөрийн бие даасан хэсгээ хийж дуусах хугацаа юм.

Гаралт

Оюутнуудыг группуудэд хувааж болох боломжийн тоо болох нэг ширхэг бүхэл тоон утгыг хэвлэ. Хариу их гарч болох учир $10^{9} + 7$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү.

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

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

Оролт
3 2
2 4 5
Гаралт
3
Оролт
4 3
7 8 9 10
Гаралт
13
Оролт
4 0
5 10 20 21
Гаралт
1

Тэмдэглэл

Эхний жишээн дээр бидэнд гурван боломж байна:

  • Эхний болон хоёр дахь оюутнууд групп болох ба гурав дахь оюутан ганцаараа групп болох. Нийт тэнцвэргүй байдал нь $2 + 0 = 2$.
  • Эхний оюутан ганцаараа групп болох ба хоёр болон гурав дахь оюутнууд групп болох. Нийт тэнцвэргүй байдал нь $0 + 1 = 1$.
  • Бүх оюутнууд ганц ганцаараа групп болох. Нийт тэнцвэргүй байдал нь $0$.

Гурав дахь жишээн дээр нийт тэнцвэргүй байдал $0$ байх ёстой ба бүх оюутнууд ганц ганцаараа групп болох ёстой.

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