codeforces-scrape

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

2193D.md (2366B)


      1 Source: https://codeforces.com/problemset/problem/2193/D
      2 
      3 D. Monster Game
      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 You have been gifted a new game called "Elatyh". In the game, you are given $n$ swords, each with its own strength. In particular, the sword numbered $i$ has a strength of $a_i$. The game consists of $n$ levels, each of which features a monster.
     22 
     23 You start at level $1$ and progress further. To pass level $i$ and move on to level $i + 1$, you need to defeat the monster at level $i$. To defeat the monster at level $i$, you need to deal it $b_i$ sword strikes. The swords in the game are very fragile, so they can only deal one strike before breaking. If you complete level $n$ or run out of swords, you can finish the game and proceed to score calculation.
     24 
     25 Before the game, you are allowed to choose the difficulty level. If you choose difficulty $x$, swords with a strength less than $x$ will not affect the monsters. The game score in this case is equal to $x$ multiplied by the number of levels completed. Your task is to choose the game difficulty in such a way as to maximize the game score.
     26 
     27 Input
     28 
     29 Each test consists of several test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The following describes the test cases.
     30 
     31 The first line of each test case contains a single integer $n$ ($1\le n\le 2 \cdot 10^5$).
     32 
     33 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ $(1\le a_i\le 10^9)$.
     34 
     35 The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ $(1\le b_i\le n)$.
     36 
     37 It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output a single integer — the maximum game score.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 5
     49 
     50 3
     51 
     52 1 3 4
     53 
     54 2 1 1
     55 
     56 2
     57 
     58 2 3
     59 
     60 1 1
     61 
     62 4
     63 
     64 1 2 3 4
     65 
     66 2 2 1 1
     67 
     68 6
     69 
     70 4 4 1 4 5 4
     71 
     72 2 2 4 1 2 2
     73 
     74 10
     75 
     76 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
     77 
     78 1 1 1 1 1 1 1 1 1 1
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 3
     85 4
     86 3
     87 8
     88 10000000000
     89 ```
     90 
     91 Note
     92 
     93 Consider the first test case. Optimal difficulty to choose is $3$. If difficulty is $3$, you can deal strikes with swords number $2$ and $3$. With $2$ swords you can complete $1$ level, so the game score is $3\cdot 1 = 3$.