codeforces-scrape

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

2051E.md (2460B)


      1 Source: https://codeforces.com/problemset/problem/2051/E
      2 
      3 E. Best Price
      4 
      5 time limit per test
      6 
      7 2 seconds
      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 A batch of Christmas trees has arrived at the largest store in Berland. $n$ customers have already come to the store, wanting to buy them.
     22 
     23 Before the sales begin, the store needs to determine the price for one tree (the price is the same for all customers). To do this, the store has some information about each customer.
     24 
     25 For the $i$-th customer, two integers $a_i$ and $b_i$ are known, which define their behavior:
     26 
     27 * if the price of the product is at most $a_i$, the customer will buy a tree and leave a positive review;
     28 * otherwise, if the price of the product is at most $b_i$, the customer will buy a tree but leave a negative review;
     29 * otherwise, the customer will not buy a tree at all.
     30 
     31 Your task is to calculate the maximum possible earnings for the store, given that it can receive no more than $k$ negative reviews.
     32 
     33 Input
     34 
     35 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $0 \le k \le n$).
     38 
     39 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^9$).
     40 
     41 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 2 \cdot 10^9$; $a_i \lt b_i$).
     42 
     43 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print a single integer — the maximum possible earnings for the store, given that it can receive no more than $k$ negative reviews.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 5
     55 
     56 2 0
     57 
     58 2 1
     59 
     60 3 4
     61 
     62 1 1
     63 
     64 2
     65 
     66 5
     67 
     68 3 3
     69 
     70 1 5 2
     71 
     72 3 6 4
     73 
     74 4 3
     75 
     76 2 3 2 8
     77 
     78 3 7 3 9
     79 
     80 3 1
     81 
     82 2 9 5
     83 
     84 12 14 9
     85 ```
     86 
     87 Output
     88 
     89 ```
     90 2
     91 5
     92 9
     93 14
     94 15
     95 ```
     96 
     97 Note
     98 
     99 Consider the example from the statement:
    100 
    101 * In the first test case, the price should be set to $1$. Then both customers will buy one tree each and leave no negative reviews;
    102 * In the second test case, the price should be set to $5$. Then the only customer will buy a tree and leave a negative review;
    103 * In the third test case, the price should be set to $3$. Then all customers will buy one tree each, and the store will receive two negative reviews.
    104 * In the fourth test case, the price should be set to $7$. Then two customers will buy one tree each, and the store will receive one negative review.