codeforces-scrape

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

1763B.md (2154B)


      1 Source: https://codeforces.com/problemset/problem/1763/B
      2 
      3 B. Incinerate
      4 
      5 time limit per test
      6 
      7 1 second
      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 To destroy humanity, The Monster Association sent $n$ monsters to Earth's surface. The $i$-th monster has health $h_i$ and power $p_i$.
     22 
     23 With his last resort attack, True Spiral Incineration Cannon, Genos can deal $k$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $k$ (if $k \gt 0$) with a single attack.
     24 
     25 However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $^\dagger$weakest monster $^\ddagger$alive. In other words, the minimum $p_i$ among all currently living monsters is subtracted from the value of $k$ after each attack.
     26 
     27 $^\dagger$The Weakest monster is the one with the least power.
     28 
     29 $^\ddagger$A monster is alive if its health is strictly greater than $0$.
     30 
     31 Will Genos be successful in killing all the monsters?
     32 
     33 Input
     34 
     35 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.
     36 
     37 The first line of each test case contains two integers, $n$ and $k$ ($1 \le n, k \le 10^5$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $n$ integers describing the arrays $h$ and $p$ ($1 \le h_i, p_i \le 10^9$).
     38 
     39 It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     40 
     41 Output
     42 
     43 For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 3
     51 
     52 6 7
     53 
     54 18 5 13 9 10 1
     55 
     56 2 7 2 1 2 6
     57 
     58 3 4
     59 
     60 5 5 5
     61 
     62 4 4 4
     63 
     64 3 2
     65 
     66 2 1 3
     67 
     68 1 1 1
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 YES
     75 NO
     76 YES
     77 ```
     78 
     79 Note
     80 
     81 In the first example, after Genos' first attack, $h$ and $k$ will update to:
     82 
     83 * $h: [11,0,6,2,3,0]$
     84 * $k: 7-1 = 6$
     85 
     86 After second attack:
     87 
     88 * $h: [5,0,0,0,0,0]$
     89 * $k: 6-2 = 4$
     90 
     91 After third attack:
     92 
     93 * $h: [1,0,0,0,0,0]$
     94 * $k: 4-2 = 2$
     95 
     96 After fourth attack:
     97 
     98 * $h: [0,0,0,0,0,0]$
     99 
    100 As Genos could kill all monsters, the answer is YES.