{"problem":{"name":"D. Guessing Messages","description":{"content":"Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages. To do that, they craft some text in such a way so that the hidden message is a subsequence of ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10230D"},"statements":[{"statement_type":"Markdown","content":"Samuelo is a very good friend of Roppa. Whenever they feel bored, they like to exchange secret messages.\n\nTo do that, they craft some text in such a way so that the hidden message is a subsequence of it. To make things harder, they never use whitespaces.\n\nAn example of message exchanged in the past is (hidden message is red and underlined):\n\nIt can be very hard to uncover a message hidden like that, but it's usually not a problem for them since their minds are pretty much in sync.\n\nSamuelo just wrote one of those messages. Roppa decided to take a step further this time and test their friendship by trying to guess the hidden message before even receiving it.\n\nGiven the message that Samuelo wrote and Roppa's guess, help Roppa on figuring out if his guess is in fact hidden in Samuelo's message.\n\nThe first line the input contains a string $s$ ($1 <= lvert s rvert <= 10^6$), indicating the message that Samuelo wrote. The second line of the input contains a string $t$ ($1 <= lvert t rvert <= 10^6$), indicating Roppa's guess.\n\nBoth strings are composed only of lowercase English letters.\n\nOutput YES if Roppa's guess is hidden in Samuelo's message. Otherwise, output NO.\n\n## Input\n\nThe first line the input contains a string $s$ ($1 <= lvert s rvert <= 10^6$), indicating the message that Samuelo wrote. The second line of the input contains a string $t$ ($1 <= lvert t rvert <= 10^6$), indicating Roppa's guess.Both strings are composed only of lowercase English letters.\n\n## Output\n\nOutput YES if Roppa's guess is hidden in Samuelo's message. Otherwise, output NO.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of features desired by Prof. Xie and Prof. Zhang, respectively.  \nLet $ W = (w_1, w_2, \\dots, w_{n+m}) \\in \\mathbb{Z}^{n+m} $ be the weight vector, where $ w_i > 0 $ is the weight of feature $ i $.  \nLet $ F_X = \\{1, 2, \\dots, n\\} $ be the set of features desired by Prof. Xie.  \nLet $ F_Z = \\{n+1, n+2, \\dots, n+m\\} $ be the set of features desired by Prof. Zhang.  \nLet $ C \\subseteq F_X \\times F_Z $ be the set of conflicting pairs, with $ |C| = k $.\n\n**Constraints**  \n1. $ 1 \\le n, m \\le 100 $  \n2. $ 1 \\le k \\le 10000 $  \n3. $ 1 \\le w_i \\le 10^7 $ for all $ i \\in \\{1, \\dots, n+m\\} $  \n4. For each conflict $ (p_i, q_i) \\in C $: $ p_i \\in F_X $, $ q_i \\in F_Z $\n\n**Objective**  \nFind a subset $ S \\subseteq F_X \\cup F_Z $ such that:  \n- $ S \\cap C = \\emptyset $ (no conflicting pair is selected),  \n- The total weight $ \\sum_{i \\in S} w_i $ is maximized.  \n\nOutput the maximum total weight.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10230D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}