codeforces-scrape

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

1310A.md (1859B)


      1 Source: https://codeforces.com/problemset/problem/1310/A
      2 
      3 A. Recommendations
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 VK news recommendation system daily selects interesting publications of one of $n$ disjoint categories for each user. Each publication belongs to exactly one category. For each category $i$ batch algorithm selects $a_i$ publications.
     22 
     23 The latest A/B test suggests that users are reading recommended publications more actively if each category has a different number of publications within daily recommendations. The targeted algorithm can find a single interesting publication of $i$-th category within $t_i$ seconds.
     24 
     25 What is the minimum total time necessary to add publications to the result of batch algorithm execution, so all categories have a different number of publications? You can't remove publications recommended by the batch algorithm.
     26 
     27 Input
     28 
     29 The first line of input consists of single integer $n$ — the number of news categories ($1 \le n \le 200\,000$).
     30 
     31 The second line of input consists of $n$ integers $a_i$ — the number of publications of $i$-th category selected by the batch algorithm ($1 \le a_i \le 10^9$).
     32 
     33 The third line of input consists of $n$ integers $t_i$ — time it takes for targeted algorithm to find one new publication of category $i$ ($1 \le t_i \le 10^5)$.
     34 
     35 Output
     36 
     37 Print one integer — the minimal required time for the targeted algorithm to get rid of categories with the same size.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5
     45 3 7 9 7 8
     46 5 2 5 7 5
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 6
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 5
     59 1 2 3 4 5
     60 1 1 1 1 1
     61 ```
     62 
     63 Output
     64 
     65 ```
     66 0
     67 ```
     68 
     69 Note
     70 
     71 In the first example, it is possible to find three publications of the second type, which will take 6 seconds.
     72 
     73 In the second example, all news categories contain a different number of publications.