Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1950. Relief
Динамическое программирование и запоминающие функцииОлимпиадные задачи на английском языке
| 22/07/2013 | Лето 2013-14 (командная) (G) |
Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Some people like to pretend that they are a pharaoh. Or a dolphin. Luka is one such person.
He has built a relief consisting of a long line of `N` columns with nonnegative integer heights. The
heights of all columns were initially zero. The relief was build in steps, where in each step Luka would
select a contiguous subsequence of columns with equal heights and raise all columns in the
subsequence, except the first and last column, by one.
Hundreds of years have passed, and some of the columns have been stolen. Luka's great-great-…-great-grandson
is trying to determine the number of possible reliefs that could have been built by Luka
such that the remaining columns' heights match the original relief.
The first line of input contains the positive integer `N` (`1\ ≤\ \ N\ \ ≤\ 10\ 000`), the number of columns in
Luka's relief.
The second line of input contains `N` space-separated integers `h_i` (`-1\ ≤\ h_i\ ≤\ 10\ 000`), the column heights.
A height of `-1` represents a stolen column.
The first and only line of output must contain the required number of possible reliefs modulo `1\ 000\ 000\ 007`.
Sample Input #1
3 -1 2 -1
Sample Output #1
0
Sample Input #2
3 -1 -1 -1
Sample Output #2
2
Sample Input #3
6 -1 -1 -1 2 -1 -1
Sample Output #3
3
