Quests (Codeforces 1914C)
Tags: Greedy, math

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$$$.Monocarp can complete quests according to the following rules:   the $$$1$$$-st quest is always available for completion;  the $$$i$$$-th quest is available for completion if all quests $$$j < i$$$ have been completed at least once. Note that Monocarp can complete the same quest multiple times.For each completion, the character gets some amount of experience points:   for the first completion of the $$$i$$$-th quest, he gets $$$a_i$$$ experience points;  for each subsequent completion of the $$$i$$$-th quest, he gets $$$b_i$$$ experience points. 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.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.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.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^3$$$).The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^3$$$).Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: 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.

Note: 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).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$$$.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$$$.

Sample Inputs:
4
4 7
4 3 1 2
1 1 1 1
3 2
1 2 5
3 1 8
5 5
3 2 4 1 4
2 3 1 4 7
6 4
1 4 5 4 5 10
1 5 1 2 5 1

Sample Outputs:
13
4
15
15

Solution (Python):
def max_points():
    (n, k) = map(int, input().split())
    arr = list(map(int, input().split()))
    dup = list(map(int, input().split()))
    sum = 0
    max_point = 0
    dup_max = 0
    for i in range(min([k, n])):
        sum += arr[i]
        if dup[i] > dup_max:
            dup_max = dup[i]
        if sum + dup_max * (k - i - 1) > max_point:
            max_point = sum + dup_max * (k - i - 1)
    print(max_point)
for _ in range(int(input())):
    max_points()

Solution (Python):
import sys
from math import *
input = sys.stdin.readline

def inp():
    return int(input())

def inlt():
    return list(map(int, input().split()))

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def solve():
    (n, k) = invr()
    a = inlt()
    b = inlt()
    maxb = 0
    suma = 0
    res = 0
    for i in range(min(n, k)):
        maxb = max(b[i], maxb)
        suma = suma + a[i]
        res = max(suma + maxb * (k - i - 1), res)
    print(res)
if __name__ == '__main__':
    t = inp()
    for i in range(t):
        solve()

Solution (Python):
import io, os, math

def yes():
    print('YES')

def no():
    print('NO')
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def I():
    return int(input())

def In():
    return map(int, input().split())

def Sn():
    return input().strip()

def dict(a):
    d = {}
    for x in a:
        if d.get(x, -1) != -1:
            d[x] += 1
        else:
            d[x] = 1
    return d

def find_gt(a, x):
    """"""
    i = bi.bisect_left(a, x)
    if i != len(a):
        return i
    else:
        return -1

def find_ge(a, x):
    """"""
    i = bi.bisect_left(a, x)
    if i != len(a):
        return i
    else:
        return -1

def main():
    try:
        (n, k) = In()
        a = list(In())
        b = list(In())
        ans = 0
        mx = 0
        for i in range(n):
            mx = max(mx, b[i])
            if i > 0:
                a[i] += a[i - 1]
            amt = 0
            if k - i > 0:
                amt += a[i]
                amt += (k - i - 1) * mx
            ans = max(amt, ans)
        print(ans)
    except:
        pass
M = 998244353
P = 1000000007
if __name__ == '__main__':
    for _ in range(I()):
        main()