codeforces-scrape

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

1951C.md (3077B)


      1 Source: https://codeforces.com/problemset/problem/1951/C
      2 
      3 C. Ticket Hoarding
      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 [Maître Gims - Est-ce que tu m'aimes ?](https://youtu.be/6TpyRE_juyA)
     22 
     23 ඞ
     24 
     25 As the CEO of a startup company, you want to reward each of your $k$ employees with a ticket to the upcoming concert. The tickets will be on sale for $n$ days, and by some time travelling, you have predicted that the price per ticket at day $i$ will be $a_i$. However, to prevent ticket hoarding, the concert organizers have implemented the following measures:
     26 
     27 * A person may purchase no more than $m$ tickets per day.
     28 * If a person purchases $x$ tickets on day $i$, all subsequent days (i.e. from day $i+1$ onwards) will have their prices per ticket increased by $x$.
     29 
     30 For example, if $a = [1, 3, 8, 4, 5]$ and you purchase $2$ tickets on day $1$, they will cost $2$ in total, and the prices from day $2$ onwards will become $[5, 10, 6, 7]$. If you then purchase $3$ more tickets on day $2$, they will cost in total an additional $15$, and the prices from day $3$ onwards will become $[13, 9, 10]$.
     31 
     32 Find the minimum spending to purchase $k$ tickets.
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.
     37 
     38 The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^9, 1 \le k \le \min(nm, 10^9)$) — the number of sale days, the maximum amount of ticket purchasable each day, and the number of tickets to be bought at the end.
     39 
     40 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the price per ticket for each of the upcoming $n$ days.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
     43 
     44 Output
     45 
     46 For each test case, print one integer: the minimum amount of money needed to purchase exactly $k$ tickets.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 4
     54 
     55 4 2 3
     56 
     57 8 6 4 2
     58 
     59 4 2 8
     60 
     61 8 6 4 2
     62 
     63 5 100 1
     64 
     65 10000 1 100 10 1000
     66 
     67 6 3 9
     68 
     69 5 5 5 5 5 5
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 10
     76 64
     77 1
     78 72
     79 ```
     80 
     81 Note
     82 
     83 In the first test case, one optimal way to buy $3$ tickets is as follows:
     84 
     85 * Buy $0$ tickets on the first day. The prices per ticket for the remaining days are $[6, 4, 2]$.
     86 * Buy $0$ tickets on the second day. The prices per ticket for the remaining days are $[4, 2]$.
     87 * Buy $1$ ticket on the third day with cost $4$. The price per ticket for the remaining day is $[3]$.
     88 * Buy $2$ tickets on the fourth day with cost $6$.
     89 
     90 In the second test case, there is only one way to buy $8$ tickets:
     91 
     92 * Buy $2$ tickets on the first day with cost $16$. The prices per ticket for the remaining days are $[8, 6, 4]$.
     93 * Buy $2$ tickets on the second day with cost $16$. The prices per ticket for the remaining days are $[8, 6]$.
     94 * Buy $2$ tickets on the third day with cost $16$. The price per ticket for the remaining day is $[8]$.
     95 * Buy $2$ tickets on the fourth day with cost $16$.