B. USB vs. PS/2

Codeforces

IDCF762B

Time2000ms

Memory256MB

Difficulty—

greedyimplementationsortingstwo pointers

English · Original

Chinese · Translation

Formal · Original

Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as possible. After all, the country is in crisis! The computers bought for the room were different. Some of them had only USB ports, some — only PS/2 ports, and some had both options. You have found a price list of a certain computer shop. In it, for _m_ mouses it is specified the cost and the type of the port that is required to plug the mouse in (USB or PS/2). Each mouse from the list can be bought at most once. You want to buy some set of mouses from the given price list in such a way so that you maximize the number of computers equipped with mouses (it is not guaranteed that you will be able to equip all of the computers), and in case of equality of this value you want to minimize the total cost of mouses you will buy. ## Input The first line contains three integers _a_, _b_ and _c_ (0 ≤ _a_, _b_, _c_ ≤ 105) — the number of computers that only have USB ports, the number of computers, that only have PS/2 ports, and the number of computers, that have both options, respectively. The next line contains one integer _m_ (0 ≤ _m_ ≤ 3·105) — the number of mouses in the price list. The next _m_ lines each describe another mouse. The _i_\-th line contains first integer _val__i_ (1 ≤ _val__i_ ≤ 109) — the cost of the _i_\-th mouse, then the type of port (USB or PS/2) that is required to plug the mouse in. ## Output Output two integers separated by space — the number of equipped computers and the total cost of the mouses you will buy. [samples] ## Note In the first example you can buy the first three mouses. This way you will equip one of the computers that has only a USB port with a USB mouse, and the two PS/2 mouses you will plug into the computer with PS/2 port and the computer with both ports.

由于贝尔兰国立大学的学生人数增加，决定配备一个新的计算机房。你被分配了购买鼠标的任务，必须尽可能少地花钱，毕竟国家正处于危机中！为房间购买的计算机各不相同：有些只有 USB 接口，有些只有 PS/2 接口，还有一些同时具备两种接口。你找到了某家电脑商店的价格清单。清单中列出了 #cf_span[m] 个鼠标，每个鼠标标明了价格和所需的接口类型（USB 或 PS/2）。清单中的每个鼠标最多只能购买一次。你需要从给定的价格清单中购买一组鼠标，使得配备鼠标的计算机数量最大化（不一定能为所有计算机都配备鼠标）；在配备计算机数量相同的情况下，你希望总花费最小。第一行包含三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[0 ≤ a, b, c ≤ 105]) —— 分别表示仅具有 USB 接口的计算机数量、仅具有 PS/2 接口的计算机数量，以及同时具备两种接口的计算机数量。第二行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m ≤ 3·105]) —— 价格清单中鼠标的数量。接下来的 #cf_span[m] 行，每行描述一个鼠标。第 #cf_span[i] 行首先是一个整数 #cf_span[vali] (#cf_span[1 ≤ vali ≤ 109]) —— 第 #cf_span[i] 个鼠标的成本，然后是其所需的接口类型（USB 或 PS/2）。请输出两个用空格分隔的整数 —— 配备鼠标的计算机数量和你购买鼠标所花费的总成本。在第一个例子中，你可以购买前三个鼠标。这样，你可以用一个 USB 鼠标为一台仅含 USB 接口的计算机配备鼠标，并将两个 PS/2 鼠标分别插入一台仅含 PS/2 接口的计算机和一台同时具备两种接口的计算机。 ## Input 第一行包含三个整数 #cf_span[a], #cf_span[b] 和 #cf_span[c] (#cf_span[0 ≤ a, b, c ≤ 105]) —— 分别表示仅具有 USB 接口的计算机数量、仅具有 PS/2 接口的计算机数量，以及同时具备两种接口的计算机数量。第二行包含一个整数 #cf_span[m] (#cf_span[0 ≤ m ≤ 3·105]) —— 价格清单中鼠标的数量。接下来的 #cf_span[m] 行，每行描述一个鼠标。第 #cf_span[i] 行首先是一个整数 #cf_span[vali] (#cf_span[1 ≤ vali ≤ 109]) —— 第 #cf_span[i] 个鼠标的成本，然后是其所需的接口类型（USB 或 PS/2）。 ## Output 请输出两个用空格分隔的整数 —— 配备鼠标的计算机数量和你购买鼠标所花费的总成本。 [samples] ## Note 在第一个例子中，你可以购买前三个鼠标。这样，你可以用一个 USB 鼠标为一台仅含 USB 接口的计算机配备鼠标，并将两个 PS/2 鼠标分别插入一台仅含 PS/2 接口的计算机和一台同时具备两种接口的计算机。

**Definitions** Let $ a, b, c \in \mathbb{Z}_{\geq 0} $ denote the number of computers with only USB, only PS/2, and both ports, respectively. Let $ m \in \mathbb{Z}_{\geq 0} $ be the number of available mouses. Let $ M = \{(v_i, t_i) \mid i \in \{1, \dots, m\}\} $ be the set of mouses, where $ v_i \in \mathbb{Z}_{\geq 1} $ is the cost and $ t_i \in \{\text{USB}, \text{PS/2}\} $ is the port type. **Constraints** 1. $ 0 \leq a, b, c \leq 10^5 $ 2. $ 0 \leq m \leq 3 \cdot 10^5 $ 3. $ 1 \leq v_i \leq 10^9 $ for all $ i \in \{1, \dots, m\} $ **Objective** Select a subset $ S \subseteq M $ to: - Maximize the number of equipped computers, subject to: - At most $ a $ USB mouses used for USB-only computers, - At most $ b $ PS/2 mouses used for PS/2-only computers, - At most $ c $ mouses (either type) used for dual-port computers. - Among all such subsets achieving maximum equipped computers, minimize total cost: $$ \sum_{(v_i, t_i) \in S} v_i $$

Samples

Input #1

2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2

Output #1

3 14

API Response (JSON)

{
  "problem": {
    "name": "B. USB vs. PS/2",
    "description": {
      "content": "Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as poss",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF762B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as poss...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "由于贝尔兰国立大学的学生人数增加，决定配备一个新的计算机房。你被分配了购买鼠标的任务，必须尽可能少地花钱，毕竟国家正处于危机中！\n\n为房间购买的计算机各不相同：有些只有 USB 接口，有些只有 PS/2 接口，还有一些同时具备两种接口。\n\n你找到了某家电脑商店的价格清单。清单中列出了 #cf_span[m] 个鼠标，每个鼠标标明了价格和所需的接口类型（USB 或 PS/2）。清单中的每个鼠标最多只...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ a, b, c \\in \\mathbb{Z}_{\\geq 0} $ denote the number of computers with only USB, only PS/2, and both ports, respectively.  \nLet $ m \\in \\mathbb{Z}_{\\geq 0} $ be the number of av...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments