codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1876A.md (2787B)


      1 Source: https://codeforces.com/problemset/problem/1876/A
      2 
      3 A. Helmets in Night Light
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Pak Chanek is the chief of a village named Khuntien. On one night filled with lights, Pak Chanek has a sudden and important announcement that needs to be notified to all of the $n$ residents in Khuntien.
     22 
     23 First, Pak Chanek shares the announcement directly to one or more residents with a cost of $p$ for each person. After that, the residents can share the announcement to other residents using a magical helmet-shaped device. However, there is a cost for using the helmet-shaped device. For each $i$, if the $i$-th resident has got the announcement at least once (either directly from Pak Chanek or from another resident), he/she can share the announcement to at most $a_i$ other residents with a cost of $b_i$ for each share.
     24 
     25 If Pak Chanek can also control how the residents share the announcement to other residents, what is the minimum cost for Pak Chanek to notify all $n$ residents of Khuntien about the announcement?
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The following lines contain the description of each test case.
     30 
     31 The first line contains two integers $n$ and $p$ ($1 \leq n \leq 10^5$; $1 \leq p \leq 10^5$) — the number of residents and the cost for Pak Chanek to share the announcement directly to one resident.
     32 
     33 The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1\leq a_i\leq10^5$) — the maximum number of residents that each resident can share the announcement to.
     34 
     35 The third line contains $n$ integers $b_1,b_2,b_3,\ldots,b_n$ ($1\leq b_i\leq10^5$) — the cost for each resident to share the announcement to one other resident.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a line containing an integer representing the minimum cost to notify all $n$ residents of Khuntien about the announcement.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 6 3
     51 
     52 2 3 2 1 1 3
     53 
     54 4 3 2 6 3 6
     55 
     56 1 100000
     57 
     58 100000
     59 
     60 1
     61 
     62 4 94
     63 
     64 1 4 2 3
     65 
     66 103 96 86 57
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 16
     73 100000
     74 265
     75 ```
     76 
     77 Note
     78 
     79 In the first test case, the following is a possible optimal strategy:
     80 
     81 1. Pak Chanek shares the announcement directly to the $3$-rd, $5$-th, and $6$-th resident. This requires a cost of $p+p+p=3+3+3=9$.
     82 2. The $3$-rd resident shares the announcement to the $1$-st and $2$-nd resident. This requires a cost of $b_3+b_3=2+2=4$.
     83 3. The $2$-nd resident shares the announcement to the $4$-th resident. This requires a cost of $b_2=3$.
     84 
     85 The total cost is $9+4+3=16$. It can be shown that there is no other strategy with a smaller cost.