Codeforces Round 581 (Div. 2) |
---|
Закончено |
Два любимых числа Наташи — это $$$n$$$ и $$$1$$$, а два любимых числа Саши — $$$m$$$ и $$$-1$$$. Однажды Саша и Наташа встретились и выписали все возможные массивы из $$$n+m$$$ элементов, в которых $$$n$$$ элементов равны $$$1$$$, а другие $$$m$$$ элементов равны $$$-1$$$. Для каждого массива они посчитали его максимальную префиксную сумму, возможно пустую, равную $$$0$$$ (т. е. если каждая непустая префиксная сумма меньше нуля, то она считается равной нулю). Более формально, обозначим за $$$f(a)$$$ максимальную префиксную сумму массива $$$a_{1, \ldots ,l}$$$ длины $$$l \geq 0$$$. Тогда:
$$$$$$f(a) = \max (0, \smash{\displaystyle\max_{1 \leq i \leq l}} \sum_{j=1}^{i} a_j )$$$$$$
Теперь они хотят посчитать сумму максимальных префиксных сумм по всем выписанным массивам и просят вас в этом помочь. Так как эта сумма может быть очень большой, выведите её по модулю $$$998\: 244\: 853$$$.
Единственная строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0 \le n,m \le 2\,000$$$).
Выведите ответ на задачу по модулю $$$998\: 244\: 853$$$.
0 2
0
2 0
2
2 2
5
2000 2000
674532367
В первом примере существует единственный возможный массив: [-1,-1], его максимальная префиксная сумма равна $$$0$$$.
Во втором примере существует единственный возможный массив: [1,1], его максимальная префиксная сумма равна $$$2$$$.
В третьем примере существуют $$$6$$$ возможных массивов:
[1,1,-1,-1], f([1,1,-1,-1]) = 2
[1,-1,1,-1], f([1,-1,1,-1]) = 1
[1,-1,-1,1], f([1,-1,-1,1]) = 1
[-1,1,1,-1], f([-1,1,1,-1]) = 1
[-1,1,-1,1], f([-1,1,-1,1]) = 0
[-1,-1,1,1], f([-1,-1,1,1]) = 0
Ответ для третьего примера равен $$$2+1+1+1+0+0 = 5$$$.
Название |
---|