codeforces-scrape

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

1106B.md (4539B)


      1 Source: https://codeforces.com/problemset/problem/1106/B
      2 
      3 B. Lunar New Year and Food Ordering
      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 Lunar New Year is approaching, and Bob is planning to go for a famous restaurant — "Alice's".
     22 
     23 The restaurant "Alice's" serves $n$ kinds of food. The cost for the $i$-th kind is always $c_i$. Initially, the restaurant has enough ingredients for serving exactly $a_i$ dishes of the $i$-th kind. In the New Year's Eve, $m$ customers will visit Alice's one after another and the $j$-th customer will order $d_j$ dishes of the $t_j$-th kind of food. The $(i + 1)$-st customer will only come after the $i$-th customer is completely served.
     24 
     25 Suppose there are $r_i$ dishes of the $i$-th kind remaining (initially $r_i = a_i$). When a customer orders $1$ dish of the $i$-th kind, the following principles will be processed.
     26 
     27 1. If $r_i \gt 0$, the customer will be served exactly $1$ dish of the $i$-th kind. The cost for the dish is $c_i$. Meanwhile, $r_i$ will be reduced by $1$.
     28 2. Otherwise, the customer will be served $1$ dish of the cheapest available kind of food if there are any. If there are multiple cheapest kinds of food, the one with the smallest index among the cheapest will be served. The cost will be the cost for the dish served and the remain for the corresponding dish will be reduced by $1$.
     29 3. If there are no more dishes at all, the customer will leave angrily. Therefore, no matter how many dishes are served previously, the cost for the customer is $0$.
     30 
     31 If the customer doesn't leave after the $d_j$ dishes are served, the cost for the customer will be the sum of the cost for these $d_j$ dishes.
     32 
     33 Please determine the total cost for each of the $m$ customers.
     34 
     35 Input
     36 
     37 The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 10^5$), representing the number of different kinds of food and the number of customers, respectively.
     38 
     39 The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^7$), where $a_i$ denotes the initial remain of the $i$-th kind of dishes.
     40 
     41 The third line contains $n$ positive integers $c_1, c_2, \ldots, c_n$ ($1 \leq c_i \leq 10^6$), where $c_i$ denotes the cost of one dish of the $i$-th kind.
     42 
     43 The following $m$ lines describe the orders of the $m$ customers respectively. The $j$-th line contains two positive integers $t_j$ and $d_j$ ($1 \leq t_j \leq n$, $1 \leq d_j \leq 10^7$), representing the kind of food and the number of dishes the $j$-th customer orders, respectively.
     44 
     45 Output
     46 
     47 Print $m$ lines. In the $j$-th line print the cost for the $j$-th customer.
     48 
     49 Examples
     50 
     51 Input
     52 
     53 ```
     54 8 5
     55 8 6 2 1 4 5 7 5
     56 6 3 3 2 6 2 3 2
     57 2 8
     58 1 4
     59 4 7
     60 3 4
     61 6 10
     62 ```
     63 
     64 Output
     65 
     66 ```
     67 22
     68 24
     69 14
     70 10
     71 39
     72 ```
     73 
     74 Input
     75 
     76 ```
     77 6 6
     78 6 6 6 6 6 6
     79 6 66 666 6666 66666 666666
     80 1 6
     81 2 6
     82 3 6
     83 4 6
     84 5 6
     85 6 66
     86 ```
     87 
     88 Output
     89 
     90 ```
     91 36
     92 396
     93 3996
     94 39996
     95 399996
     96 0
     97 ```
     98 
     99 Input
    100 
    101 ```
    102 6 6
    103 6 6 6 6 6 6
    104 6 66 666 6666 66666 666666
    105 1 6
    106 2 13
    107 3 6
    108 4 11
    109 5 6
    110 6 6
    111 ```
    112 
    113 Output
    114 
    115 ```
    116 36
    117 11058
    118 99996
    119 4333326
    120 0
    121 0
    122 ```
    123 
    124 Note
    125 
    126 In the first sample, $5$ customers will be served as follows.
    127 
    128 1. Customer $1$ will be served $6$ dishes of the $2$-nd kind, $1$ dish of the $4$-th kind, and $1$ dish of the $6$-th kind. The cost is $6 \cdot 3 + 1 \cdot 2 + 1 \cdot 2 = 22$. The remain of the $8$ kinds of food will be $\{8, 0, 2, 0, 4, 4, 7, 5\}$.
    129 2. Customer $2$ will be served $4$ dishes of the $1$-st kind. The cost is $4 \cdot 6 = 24$. The remain will be $\{4, 0, 2, 0, 4, 4, 7, 5\}$.
    130 3. Customer $3$ will be served $4$ dishes of the $6$-th kind, $3$ dishes of the $8$-th kind. The cost is $4 \cdot 2 + 3 \cdot 2 = 14$. The remain will be $\{4, 0, 2, 0, 4, 0, 7, 2\}$.
    131 4. Customer $4$ will be served $2$ dishes of the $3$-rd kind, $2$ dishes of the $8$-th kind. The cost is $2 \cdot 3 + 2 \cdot 2 = 10$. The remain will be $\{4, 0, 0, 0, 4, 0, 7, 0\}$.
    132 5. Customer $5$ will be served $7$ dishes of the $7$-th kind, $3$ dishes of the $1$-st kind. The cost is $7 \cdot 3 + 3 \cdot 6 = 39$. The remain will be $\{1, 0, 0, 0, 4, 0, 0, 0\}$.
    133 
    134 In the second sample, each customer is served what they order except the last one, who leaves angrily without paying. For example, the second customer is served $6$ dishes of the second kind, so the cost is $66 \cdot 6 = 396$.
    135 
    136 In the third sample, some customers may not be served what they order. For example, the second customer is served $6$ dishes of the second kind, $6$ of the third and $1$ of the fourth, so the cost is $66 \cdot 6 + 666 \cdot 6 + 6666 \cdot 1 = 11058$.