B. Ali and Wi-Fi

Codeforces

IDCF10191B

Time6000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Ali lives in a very crowded city and a very large apartment. His apartment looks like an almost infinite 2D plane. In this city almost all his neighbors have WiFi networks, except for him. Precisely, from his apartment his laptop can receive N WiFi networks. One day Ali wrote a program that can hack his neighbors' WiFi networks. Furthermore, he learned how to stand in a point, hack almost all the WiFi networks that reaches that point, and join them in one ultra-speed network. Each WiFi network is described as a circle with its center on the point (x, y), a radius equal to R and a network speed equal to S. However, Ali's program can join at most M networks. When Ali's program joins many networks, the resulting network will have the total sum for speeds of all networks. Ali wants to choose a point at his apartment that will get him the maximum total speed of WiFi networks. Can you help him calculate the maximum total WiFi network speed he can get if he chooses his location optimally? The first line contains an integer T, the number of test cases. The first line of each test contains (1 ≤ N ≤ 100) the number of WiFi networks and (1 ≤ M ≤ 100) the maximum number of networks Ali can join. The following N line contains the description of N WiFi networks. The center coordinates (0 ≤ x, y ≤ 103) , the radius (1 ≤ R ≤ 103) and the network speed (0 ≤ S ≤ 106) . For each test case print a single line, containing a single integer, denoting the maximum total WiFi network speed Ali can get, if he chooses his location optimally. ## Input The first line contains an integer T, the number of test cases. The first line of each test contains (1 ≤ N ≤ 100) the number of WiFi networks and (1 ≤ M ≤ 100) the maximum number of networks Ali can join. The following N line contains the description of N WiFi networks. The center coordinates (0 ≤ x, y ≤ 103) , the radius (1 ≤ R ≤ 103) and the network speed (0 ≤ S ≤ 106) . ## Output For each test case print a single line, containing a single integer, denoting the maximum total WiFi network speed Ali can get, if he chooses his location optimally. [samples]

**Definitions** Let $ N, K \in \mathbb{Z} $ with $ 1 \leq N \leq 2000 $, $ 1 < K \leq N $. Let $ F = \{f_1, f_2, \dots, f_N\} $ be the set of friends, where each friend $ f_i $ has eating times: - $ a_i \in \mathbb{Z}^+ $: appetizer time, - $ e_i \in \mathbb{Z}^+ $: entrée time, - $ d_i \in \mathbb{Z}^+ $: dessert time. Let $ S \subseteq F $ with $ |S| = K $ be the selected subset of friends to dine with. **Constraints** 1. $ 1 \leq a_i, e_i, d_i \leq 10^9 $ for all $ i \in \{1, \dots, N\} $. 2. $ |S| = K $. **Objective** Minimize the total meal time: $$ \min_{\substack{S \subseteq F \\ |S| = K}} \left( \max_{f_i \in S} a_i + \max_{f_i \in S} e_i + \max_{f_i \in S} d_i \right) $$

API Response (JSON)

{
  "problem": {
    "name": "B. Ali and Wi-Fi",
    "description": {
      "content": "Ali lives in a very crowded city and a very large apartment. His apartment looks like an almost infinite 2D plane. In this city almost all his neighbors have WiFi networks, except for him. Precisely, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10191B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ali lives in a very crowded city and a very large apartment. His apartment looks like an almost infinite 2D plane. In this city almost all his neighbors have WiFi networks, except for him. Precisely, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N, K \\in \\mathbb{Z} $ with $ 1 \\leq N \\leq 2000 $, $ 1 < K \\leq N $.  \nLet $ F = \\{f_1, f_2, \\dots, f_N\\} $ be the set of friends, where each friend $ f_i $ has eating times:  ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments