Monsters Attack! (Codeforces 1923B)
Tags: Greedy, dp

You are playing a computer game. The current level of this game can be modeled as a straight line. Your character is in point $$$0$$$ of this line. There are $$$n$$$ monsters trying to kill your character; the $$$i$$$-th monster has health equal to $$$a_i$$$ and is initially in the point $$$x_i$$$.Every second, the following happens:  first, you fire up to $$$k$$$ bullets at monsters. Each bullet targets exactly one monster and decreases its health by $$$1$$$. For each bullet, you choose its target arbitrary (for example, you can fire all bullets at one monster, fire all bullets at different monsters, or choose any other combination). Any monster can be targeted by a bullet, regardless of its position and any other factors;  then, all alive monsters with health $$$0$$$ or less die;  then, all alive monsters move $$$1$$$ point closer to you (monsters to the left of you increase their coordinates by $$$1$$$, monsters to the right of you decrease their coordinates by $$$1$$$). If any monster reaches your character (moves to the point $$$0$$$), you lose. Can you survive and kill all $$$n$$$ monsters without letting any of them reach your character?

Input: The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 3 \cdot 10^4$$$) — the number of test cases.Each test case consists of three lines:  the first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 2 \cdot 10^9$$$);  the second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);  the third line contains $$$n$$$ integers $$$x_1, x_2, \dots, x_n$$$ ($$$-n \le x_1 < x_2 < x_3 < \dots < x_n \le n$$$; $$$x_i \ne 0$$$). Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: For each test case, print YES if you can kill all $$$n$$$ monsters before they reach your character, or NO otherwise.You can output each letter of the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will all be recognized as positive responses.

Note: In the first example, you can act as follows:  during the $$$1$$$-st second, fire $$$1$$$ bullet at the $$$1$$$-st monster and $$$1$$$ bullet at the $$$3$$$-rd monster. Then the $$$1$$$-st monster dies, the $$$2$$$-nd and the $$$3$$$-rd monster move closer;  during the $$$2$$$-nd second, fire $$$2$$$ bullets at the $$$2$$$-nd monster. Then the $$$2$$$-nd monster dies, the $$$3$$$-rd monster moves closer;  during the $$$3$$$-rd second, fire $$$2$$$ bullets at the $$$3$$$-rd monster. Then the $$$3$$$-rd monster dies. In the second example, you can fire only $$$1$$$ bullet, so you can kill only one of the two monsters during the $$$1$$$-st second. Then, the remaining monster moves closer and kills your character.

Sample Inputs:
5
3 2
1 2 3
-1 2 3
2 1
1 1
-1 1
4 10
3 4 2 5
-3 -2 1 3
5 3
2 1 3 2 5
-3 -2 3 4 5
2 1
1 2
1 2

Sample Outputs:
YES
NO
YES
YES
NO

Solution (Python):
import sys
import math
import collections
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 list(map(int, input().split()))
for i in range(int(input())):
    (n, k) = invr()
    health = inlt()
    pos = inlt()
    list_monster = [0] * (n + 1)
    sum_h = 0
    ans = False
    for (idx, p) in enumerate(pos):
        list_monster[abs(p)] += health[idx]
    for i in range(1, n + 1):
        sum_h += list_monster[i]
        if sum_h > k * i:
            ans = True
            print('NO')
            break
    if not ans:
        print('YES')

Solution (Python):
import sys
import itertools
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    x = list(map(int, input().split()))
    s = [0] * (n + 1)
    for i in range(n):
        s[abs(x[i])] += a[i]
    prefix_sum = list(itertools.accumulate(s))
    works = True
    for i in range(n + 1):
        if k * i < prefix_sum[i]:
            works = False
            break
    print('YES' if works else 'NO')

Solution (Python):
import sys
import math
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    x = list(map(int, input().split()))
    dp = dict()
    i = 0
    while i < n and x[i] < 0:
        i += 1
    j = i - 1
    tot = 0
    out = False
    while j >= 0 and i < n:
        if abs(x[j]) == x[i]:
            tot += a[i] + a[j]
            if tot > k * x[i]:
                print('NO')
                out = True
                break
            i += 1
            j -= 1
        elif abs(x[j]) < x[i]:
            tot += a[j]
            if tot > k * abs(x[j]):
                print('NO')
                out = True
                break
            j -= 1
        else:
            tot += a[i]
            if tot > k * x[i]:
                print('NO')
                out = True
                break
            i += 1
    if out:
        continue
    while j >= 0 and i == n:
        tot += a[j]
        if tot > k * abs(x[j]):
            print('NO')
            out = True
            break
        j -= 1
    if out:
        continue
    while j < 0 and i < n:
        tot += a[i]
        if tot > k * x[i]:
            print('NO')
            out = True
            break
        i += 1
    if out:
        continue
    print('YES')