Save the Magazines (Codeforces 1743C)
Tags: Greedy, dp

Monocarp has been collecting rare magazines for quite a while, and now he has decided to sell them. He distributed the magazines between $$$n$$$ boxes, arranged in a row. The $$$i$$$-th box contains $$$a_i$$$ magazines. Some of the boxes are covered with lids, others are not. Suddenly it started to rain, and now Monocarp has to save as many magazines from the rain as possible. To do this, he can move the lids between boxes as follows: if the $$$i$$$-th box was covered with a lid initially, he can either move the lid from the $$$i$$$-th box to the box $$$(i-1)$$$ (if it exists), or keep the lid on the $$$i$$$-th box. You may assume that Monocarp can move the lids instantly at the same moment, and no lid can be moved more than once. If a box will be covered with a lid after Monocarp moves the lids, the magazines in it will be safe from the rain; otherwise they will soak.You have to calculate the maximum number of magazines Monocarp can save from the rain.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of the testcases.The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of boxes.The second line contains a string of $$$n$$$ characters 0 and/or 1. If the $$$i$$$-th character is 1, the $$$i$$$-th box is initially covered with a lid. If the $$$i$$$-th character is 0, the $$$i$$$-th box is initially not covered.The third line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ is the number of magazines in the $$$i$$$-th box.The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each testcase, print one integer — the maximum number of magazines Monocarp can save from the rain.

Note: In the first testcase of the example, Monocarp can move the lid from the second box to the first box, so the boxes $$$1$$$, $$$3$$$ and $$$4$$$ are covered, and $$$10 + 8 + 9 = 27$$$ magazines are saved.In the second testcase, Monocarp can move the lid from the second box to the first box, then from the third box to the second box, then from the fifth box to the fourth box, and then from the sixth box to the fifth box. The boxes $$$1$$$, $$$2$$$, $$$4$$$ and $$$5$$$ will be covered, so $$$20 + 10 + 30 + 20 = 80$$$ magazines can be saved.There are no lids in the third testcase, so it's impossible to save even a single magazine.

Sample Inputs:
4
5
01110
10 5 8 9 6
6
011011
20 10 9 30 20 19
4
0000
100 100 100 100
4
0111
5 4 5 1

Sample Outputs:
27
80
0
14

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1 << 30)

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 = inp()
    s = insr()
    a = inlt()
    ans = 0
    idx = 0
    while idx < n:
        if s[idx] == '1':
            ans += a[idx]
            idx += 1
        else:
            c = a[idx]
            total = c
            idx += 1
            while idx < n and s[idx] == '1':
                c = min(c, a[idx])
                total += a[idx]
                idx += 1
            ans += total - c
    print(ans)
if __name__ == '__main__':
    for _ in range(inp()):
        solve()

Solution (Python):
import sys
import sys, threading
from heapq import heapify, heappop, heappush
from math import log10, floor, pow, gcd, sqrt, inf
from collections import defaultdict, deque
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 main():
    tests = inp()
    for test in range(tests):
        numOfBoxes = inp()
        lid = insr()
        boxes = inlt()
        lid.append('0')
        boxes.append(0)
        currTotal = 0
        currMin = 0
        for i in range(numOfBoxes + 1):
            if lid[i] == '0':
                currTotal = currTotal - currMin + boxes[i]
                currMin = boxes[i]
            else:
                currTotal += boxes[i]
                currMin = min(currMin, boxes[i])
        print(currTotal)
main()

Solution (Python):
import sys
from os import path
if path.exists('Input.txt'):
    sys.stdin = open('Input.txt', 'r')
    sys.stdout = open('Output.txt', 'w')
import math
from math import gcd, floor, sqrt, log, ceil, inf
from collections import *
from collections import deque as deq
from collections import Counter as cnt
from bisect import bisect_left as bl
from bisect import bisect_right as br

def li():
    return list(map(int, sys.stdin.readline().split()))

def mp():
    return map(int, sys.stdin.readline().split())

def inp():
    return int(sys.stdin.readline())

def st():
    return str(input())

def strip():
    return list(sys.stdin.readline().strip())

def pr(n):
    return sys.stdout.write(str(n) + '\n')

def prl(n):
    return sys.stdout.write(str(n) + ' ')

def prlist(a):
    print(''.join(a))
mod = 1000000007
(maximum, minimum) = (float('inf'), float('-inf'))
bi = lambda n: bin(n).replace('0b', '')
yes = lambda : print('YES')
no = lambda : print('NO')
import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(op.mul, range(n, n - r, -1), 1)
    denom = reduce(op.mul, range(1, r + 1), 1)
    return numer // denom

def fact(n):
    return math.factorial(n)

def perfect(n):
    return floor(sqrt(n)) == ceil(sqrt(n))

def lcm(a, b):
    return a * b // gcd(a, b)

def binarySearch(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return -1

def isPrime(n):
    if n % 2 == 0 and n != 2 or n < 2:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

def expo(a, n, M):
    ans = 1
    while n > 0:
        last_bit = n & 1
        if last_bit:
            ans = ans * a % M
        a = a * a % M
        n = n >> 1
    return ans

def solve():
    n = inp()
    s = strip()
    a = li()
    (ans, m, l, x) = (0, minimum, [], 0)
    for i in s:
        f = True
        if i == '1':
            if a[x] > m:
                ans += a[x]
            else:
                ans += m
        if i == '0':
            f = False
        if a[x] < m:
            f = False
        if not f:
            m = a[x]
        x += 1
    pr(ans)
for pratyush in range(inp()):
    solve()