시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 84 | 46 | 43 | 64.179% |
Farmer John's $N$ cows ($2 \leq N \leq 3\cdot 10^5$), conveniently numbered $1 \ldots N$ as usual, have ordered themselves according to a permutation $p_1,p_2,\ldots,p_N$ of $1\ldots N$. You are also given a string of length $N-1$ consisting of the letters U and D. Please find the maximum $K\le N-1$ such that there exists a subsequence $a_0,a_1,\ldots,a_{K}$ of $p$ such that for all $1\le j\le K$, $a_{j - 1} < a_j$ if the $j$th letter in the string is U, and $a_{j - 1} > a_j$ if the $j$th letter in the string is D.
The first line contains $N$.
The second line contains $p_1,p_2,\ldots,p_N$.
The last line contains the string.
Write out maximum possible value of $K$.
5 1 5 3 4 2 UDUD
4
We can choose $[a_0,a_1,a_2,a_3,a_4]=[p_1,p_2,p_3,p_4,p_5]$; the entire permutation is consistent with the string.
5 1 5 3 4 2 UUDD
3
We can choose $[a_0,a_1,a_2,a_3]=[p_1,p_3,p_4,p_5]$.