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.

Problem credits: Danny Mittal

SCORING

• Test cases 3-4 satisfy \(N\le 500\).
• Test cases 5-8 satisfy \(N\le 5000\).
• In test cases 9-12, the string consists of Us followed by Ds.
• Test cases 13-22 satisfy no additional constraints.

Problem credits: Danny Mittal

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\).

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum