Codeforces Round 621 (Div. 1 + Div. 2) |
---|
Закончено |
После удачного года по количеству удоя, Фермер Джон решил наградить своих коров их любимым угощением: вкусной травой!
На поле располагается ряд из $$$n$$$ единиц травы, каждая единица соответствующего уровня сладости $$$s_i$$$. У Фермера Джона $$$m$$$ коров, каждая обладает своим любимым уровнем сладости $$$f_i$$$ и уровнем голода $$$h_i$$$. Фермер Джон хочет выбрать непересекающиеся подмножества коров, чтобы разместить их с левой и правой стороны ряда травы. Нет никаких ограничений на количество коров с каждой стороны. Поведение коров описывается следующим образом:
Заметим, что трава не отрастает обратно. Также, чтобы не расстраивать корову, Фермер Джон может просто не выбрать каких-то коров.
Удивительно, но Фермер Джон решил, что спящие коровы — наиболее удовлетворенные. Если Фермер Джон будет выбирать порядок оптимально, то какое наибольшее количество спящих коров он сможет получить, и сколько способов существует выбрать два подмножества так, чтобы получить данное максимальное количество спящих коров (по модулю $$$10^9+7$$$)? Порядок, в котором Фермер Джон посылает коров кормиться не важен пока ни одна корова не расстроена.
В первой строке задано два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 5000$$$, $$$1 \le m \le 5000$$$) — количество единиц травы в ряду и количество коров.
Во второй строке задано $$$n$$$ целых чисел $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le n$$$) — уровни сладости травы.
В $$$i$$$-й из следующих $$$m$$$ строк задано два целых числа $$$f_i$$$ и $$$h_i$$$ ($$$1 \le f_i, h_i \le n$$$) — любимый уровень сладости и уровень голода $$$i$$$-й коровы. Никакие две коровы не имеют одинаковый любимый уровень сладости и уровень голода одновременно.
Выведите два числа — максимальное количество спящих коров и количество способов его получить по модулю $$$10^9+7$$$.
5 2 1 1 1 1 1 1 2 1 3
2 2
5 2 1 1 1 1 1 1 2 1 4
1 4
3 2 2 3 2 3 1 2 1
2 4
5 1 1 1 1 1 1 2 5
0 1
В первом примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$2$$$ спящих коров:
Во втором примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$1$$$ спящую корову:
В третьем примере, Фермер Джон может выстроить коров следующим образом, чтобы получить в итоге $$$2$$$ спящих коров:
В четвертом примере, Фермер Джон не может получить ни одной спящей коровы, а потому не будет ни одной коровы стоящей с какой-либо стороны.
Название |
---|