codeforces-scrape

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

1914C.md (2689B)


      1 Source: https://codeforces.com/problemset/problem/1914/C
      2 
      3 C. Quests
      4 
      5 time limit per test
      6 
      7 2.5 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 Monocarp is playing a computer game. In order to level up his character, he can complete quests. There are $n$ quests in the game, numbered from $1$ to $n$.
     22 
     23 Monocarp can complete quests according to the following rules:
     24 
     25 * the $1$-st quest is always available for completion;
     26 * the $i$-th quest is available for completion if all quests $j \lt i$ have been completed at least once.
     27 
     28 Note that Monocarp can complete the same quest multiple times.
     29 
     30 For each completion, the character gets some amount of experience points:
     31 
     32 * for the first completion of the $i$-th quest, he gets $a_i$ experience points;
     33 * for each subsequent completion of the $i$-th quest, he gets $b_i$ experience points.
     34 
     35 Monocarp is a very busy person, so he has free time to complete no more than $k$ quests. Your task is to calculate the maximum possible total experience Monocarp can get if he can complete no more than $k$ quests.
     36 
     37 Input
     38 
     39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     40 
     41 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 2 \cdot 10^5$) — the number of quests and the maximum number of quests Monocarp can complete, respectively.
     42 
     43 The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^3$).
     44 
     45 The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^3$).
     46 
     47 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 Output
     50 
     51 For each test case, print a single integer — the maximum possible total experience Monocarp can get if he can complete no more than $k$ quests.
     52 
     53 Example
     54 
     55 Input
     56 
     57 ```
     58 4
     59 
     60 4 7
     61 
     62 4 3 1 2
     63 
     64 1 1 1 1
     65 
     66 3 2
     67 
     68 1 2 5
     69 
     70 3 1 8
     71 
     72 5 5
     73 
     74 3 2 4 1 4
     75 
     76 2 3 1 4 7
     77 
     78 6 4
     79 
     80 1 4 5 4 5 10
     81 
     82 1 5 1 2 5 1
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 13
     89 4
     90 15
     91 15
     92 ```
     93 
     94 Note
     95 
     96 In the first test case, one of the possible quest completion sequences is as follows: $1, 1, 2, 3, 2, 4, 4$; its total experience is equal to $\underline{4} + 1 + \underline{3} + \underline{1} + 1 + \underline{2} + 1 = 13$ (the underlined numbers correspond to the instances when we complete a quest for the first time).
     97 
     98 In the second test case, one of the possible quest completion sequences is as follows: $1, 1$; its total experience is equal to $\underline{1} + 3 = 4$.
     99 
    100 In the third test case, one of the possible quest completion sequences is as follows: $1, 2, 2, 2, 3$; its total experience is equal to $\underline{3} + \underline{2} + 3 + 3 + \underline{4} = 15$.