codeforces-scrape

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

1839B.md (3799B)


      1 Source: https://codeforces.com/problemset/problem/1839/B
      2 
      3 B. Lamps
      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 You have $n$ lamps, numbered by integers from $1$ to $n$. Each lamp $i$ has two integer parameters $a_i$ and $b_i$.
     22 
     23 At each moment each lamp is in one of three states: it may be turned on, turned off, or broken.
     24 
     25 Initially all lamps are turned off. In one operation you can select one lamp that is turned off and turn it on (you can't turn on broken lamps). You receive $b_i$ points for turning lamp $i$ on. The following happens after each performed operation:
     26 
     27 * Let's denote the number of lamps that are turned on as $x$ (broken lamps do not count). All lamps $i$ such that $a_i \le x$ simultaneously break, whether they were turned on or off.
     28 
     29 Please note that broken lamps never count as turned on and that after a turned on lamp breaks, you still keep points received for turning it on.
     30 
     31 You can perform an arbitrary number of operations.
     32 
     33 Find the maximum number of points you can get.
     34 
     35 Input
     36 
     37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     38 
     39 The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of lamps.
     40 
     41 Each of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n, 1 \le b_i \le 10^9$) — parameters of the $i$-th lamp.
     42 
     43 It is guaranteed that sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, output one integer — the maximum number of points you can get.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 4
     55 
     56 4
     57 
     58 2 2
     59 
     60 1 6
     61 
     62 1 10
     63 
     64 1 13
     65 
     66 5
     67 
     68 3 4
     69 
     70 3 1
     71 
     72 2 5
     73 
     74 3 2
     75 
     76 3 3
     77 
     78 6
     79 
     80 1 2
     81 
     82 3 4
     83 
     84 1 4
     85 
     86 3 4
     87 
     88 3 5
     89 
     90 2 3
     91 
     92 1
     93 
     94 1 1
     95 ```
     96 
     97 Output
     98 
     99 ```
    100 15
    101 14
    102 20
    103 1
    104 ```
    105 
    106 Note
    107 
    108 In first test case $n = 4$. One of ways to get the maximum number of points is as follows:
    109 
    110 * You turn lamp $4$ on and receive $b_4 = 13$ points.
    111 * The number of lamps that are turned on is $1$, so all lamps with $a_i \le 1$ (namely lamps $2$, $3$ and $4$) break. Lamp $4$ is no longer turned on, so the number of lamps that are turned becomes $0$.
    112 * The only lamp you can turn on is lamp $1$, as all other lamps are broken. You receive $b_1 = 2$ points for turning it on.
    113 * The number of lamps that are turned on is $1$. As $a_1 = 2$, lamp $1$ doesn't break.
    114 
    115 Your receive $13 + 2 = 15$ points in total. It can be shown that this is the maximum number of points you can get, so the answer for the first test case is $15$.
    116 
    117 In the second test case, one of the ways to get the maximum number of points is as follows:
    118 
    119 * On the first operation you turn on lamp $4$ and receive $2$ points. No lamps break after the first operation.
    120 * On the second operation you turn on lamp $3$ and receive $5$ points. After the second operation, there are $2$ lamps turned on. As $a_3 \le 2$, lamp $3$ breaks.
    121 * On the third operation, you turn on lamp $1$ and receive $4$ points.
    122 * On the fourth operation, you turn on lamp $5$ and receive $3$ points. After that there are $3$ lamps turned on: lamps $1$, $4$ and $5$. Lamps $1$, $2$, $4$ and $5$ simultaneously break, because for all of them $a_i \le 3$.
    123 
    124 You receive $2 + 5 + 4 + 3 = 14$ points in total. It can be shown that this is the maximum number of points you can get.
    125 
    126 In the third test case, one of the ways to get the maximum number of points is as follows:
    127 
    128 * Turn the lamp $3$ on and receive $4$ points. Lamps $1$ and $3$ break.
    129 * Turn the lamp $2$ on and receive $4$ points.
    130 * Turn the lamp $6$ on and receive $3$ points. Lamp $6$ breaks.
    131 * Turn the lamp $4$ on and receive $4$ points.
    132 * Turn the lamp $5$ on and receive $5$ points. Lamps $2$, $4$ and $5$ break.
    133 
    134 You receive $4 + 4 + 3 + 4 + 5 = 20$ points in total. It can be shown that this is the maximum number of points you can get.