English · Original
Chinese · Translation
Formal · Original
You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!
Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n and a is a sequence of integers of length n - 2.
The first line, contains an integer n. (3 ≤ n ≤ 105).
The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.
Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2).
Print t in the only line of output.
## Input
The first line, contains an integer n. (3 ≤ n ≤ 105).The second line, contains string s. The third line contains n - 2 integers a1, a2, ..., an - 2 seperated by space.Each character of s is a lower case English letter (1 ≤ ai ≤ n and 1 ≤ i ≤ n - 2).
## Output
Print t in the only line of output.
[samples]
地牢中的零级骑士陷入困境！该地牢可抽象为一条长度为 $D$ 的长路径，骑士初始位于位置 0。地牢中会发生两种事件：
作为骑士，他绝不能后退。他的路上有 $n$ 个怪物和 $m$ 个商店，第 $i$ 个怪物位于位置 $a_i$，生命值为 $h_i$，若他无法击败它，则需要花费 $f_i$ 枚金币通过。第 $i$ 个商店位于位置 $b_i$，出售能将其生命值提升至 $l_i$ 的药水，购买该药水需要 $w_i$ 枚金币。
他通过地牢所需的最少金币数是多少？
第一行包含三个整数 $D, n, m$ $(1 lt.eq D lt.eq 10^9, 1 lt.eq n, m lt.eq 10^5)$。
接下来 $n$ 行，每行包含三个整数 $a_i, h_i, f_i$ $(1 lt.eq a_i lt.eq D, 1 lt.eq h_i, f_i lt.eq 10^9)$。
接下来 $m$ 行，每行包含三个整数 $b_i, l_i, w_i$ $(1 lt.eq b_i lt.eq D, 1 lt.eq l_i, w_i lt.eq 10^9)$。
所有怪物和商店的位置互不相同。
输出骑士通过地牢所需的最少金币数。
在第一个示例中，一种最优解如下：
在第一个怪物处，他支付 $30$ 枚金币通过。
在第一个商店，他花费 $10$ 枚金币购买魔法药水。
他可以用当前生命值 $5$ 击败第二个怪物。
在第三个怪物处，他支付 $100$ 枚金币通过。
在第二个商店，他什么也不买。
在第三个商店，他花费 $50$ 枚金币购买魔法药水，恢复至生命值 $30$。
他可以轻松击败最后一个怪物。
总花费为 $30 + 10 + 100 + 50 = 190$。
## Input
第一行包含三个整数 $D, n, m$ $(1 lt.eq D lt.eq 10^9, 1 lt.eq n, m lt.eq 10^5)$。接下来 $n$ 行，每行包含三个整数 $a_i, h_i, f_i$ $(1 lt.eq a_i lt.eq D, 1 lt.eq h_i, f_i lt.eq 10^9)$。接下来 $m$ 行，每行包含三个整数 $b_i, l_i, w_i$ $(1 lt.eq b_i lt.eq D, 1 lt.eq l_i, w_i lt.eq 10^9)$。所有怪物和商店的位置互不相同。
## Output
骑士通过地牢所需的最少金币数。
[samples]
## Note
在第一个示例中，一种最优解如下：在第一个怪物处，他支付 $30$ 枚金币通过。在第一个商店，他花费 $10$ 枚金币购买魔法药水。他可以用当前生命值 $5$ 击败第二个怪物。在第三个怪物处，他支付 $100$ 枚金币通过。在第二个商店，他什么也不买。在第三个商店，他花费 $50$ 枚金币购买魔法药水，恢复至生命值 $30$。他可以轻松击败最后一个怪物。总花费为 $30 + 10 + 100 + 50 = 190$。
**Definitions**
Let $ D \in \mathbb{Z}^+ $ be the length of the dungeon.
Let $ M = \{(a_i, h_i, f_i) \mid i \in \{1, \dots, n\} \} $ be the set of monsters, where $ a_i $ is position, $ h_i $ is health, and $ f_i $ is fee to bypass.
Let $ S = \{(b_i, l_i, w_i) \mid i \in \{1, \dots, m\} \} $ be the set of shops, where $ b_i $ is position, $ l_i $ is health level restored, and $ w_i $ is cost.
Let $ P = \text{sorted}(\{0\} \cup \{a_i \mid (a_i, h_i, f_i) \in M\} \cup \{b_i \mid (b_i, l_i, w_i) \in S\} \cup \{D\}) $ be the ordered sequence of key positions.
Let $ \text{health}(x) $ denote the knight’s health just before reaching position $ x $, initialized to $ 0 $ at $ x = 0 $.
Let $ \text{cost} $ denote total coins spent, initialized to $ 0 $.
**Constraints**
1. $ 1 \le D \le 10^9 $
2. $ 1 \le n, m \le 10^5 $
3. All positions in $ M \cup S $ are distinct and lie in $ [1, D] $.
4. The knight moves only forward, from position $ 0 $ to $ D $.
5. At each monster at $ a_i $: if current health $ < h_i $, must pay $ f_i $ coins to bypass; otherwise, pass without cost.
6. At each shop at $ b_i $: may optionally pay $ w_i $ coins to set current health to $ l_i $.
**Objective**
Minimize total coins spent to reach position $ D $, subject to:
- At each monster position $ a_i $, $ \text{health}(a_i) \ge h_i $ or pay $ f_i $.
- At each shop position $ b_i $, may upgrade health to $ l_i $ at cost $ w_i $.
- Health is non-decreasing and starts at $ 0 $.
Formally, find:
$$
\min \sum_{\text{bypasses}} f_i + \sum_{\text{purchases}} w_j
$$
over all valid sequences of bypasses and potion purchases, such that health constraints at monsters are satisfied.
API Response (JSON)
{
"problem": {
"name": "P. Proooooooooooooofer",
"description": {
"content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it! Encryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFP"
},
"statements": [
{
"statement_type": "Markdown",
"content": "You are given an encrypted string, encrypted using a certain algorithm. Decrypt it!\n\nEncryption algorithm gives a string t of length n and converts it to a pair (s, a) where s is a string of length n ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "地牢中的零级骑士陷入困境！该地牢可抽象为一条长度为 $D$ 的长路径，骑士初始位于位置 0。地牢中会发生两种事件：\n\n作为骑士，他绝不能后退。他的路上有 $n$ 个怪物和 $m$ 个商店，第 $i$ 个怪物位于位置 $a_i$，生命值为 $h_i$，若他无法击败它，则需要花费 $f_i$ 枚金币通过。第 $i$ 个商店位于位置 $b_i$，出售能将其生命值提升至 $l_i$ 的药水，购买该药水需要...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ D \\in \\mathbb{Z}^+ $ be the length of the dungeon. \nLet $ M = \\{(a_i, h_i, f_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of monsters, where $ a_i $ is position, $ h_i $ is h...",
"is_translate": false,
"language": "Formal"
}
]
}