Earn or Unlock (Codeforces 1854B)
Tags: DP, bitmasks

Andrea is playing the game Tanto Cuore.  He has a deck of $$$n$$$ cards with values $$$a_1, \ldots, a_n$$$ from top to bottom. Each card can be either locked or unlocked. Initially, only the topmost card is unlocked. The game proceeds in turns. In each turn, Andrea chooses an unlocked card in the deck — the value written on the card is $$$v$$$ — and performs exactly one of the following two operations:   Unlock the first $$$v$$$ locked cards in the deck from the top. If there are less than $$$v$$$ locked cards in the deck, then unlock all the locked cards.  Earn $$$v$$$ victory points.  In both cases, after performing the operation, he removes the card from the deck.The game ends when all the cards remaining in the deck are locked, or there are no more cards in the deck.What is the maximum number of victory points Andrea can earn?

Input: The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of cards in the deck.The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$0 \leq a_1, \ldots, a_n \leq n$$$) — the values of the cards in the deck.

Output: Output a single integer — the maximum number of victory points Andrea can earn.

Note: In the first sample test, the deck starts as [unlocked, locked]. Then, Andrea uses the first card to unlock the second card. Then he uses the second card to earn $$$2$$$ victory points.In the second sample test, Andrea can use the first card to unlock the second and the third card. Then he uses the second and the third card to earn $$$4+5=9$$$ victory points.In the third sample test, Andrea can't unlock any cards or gain any victory points with the first card.

Sample Inputs:
2
1 2

5
2 4 5 0 1

4
0 4 4 4

Sample Outputs:
2

9

0

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

def highest_set_bit(xy):
    return xy.bit_length() - 1

def lowest_set_bit(xy):
    return highest_set_bit(xy ^ xy - 1)
nr = int(input())
A = [int(xy) for xy in input().split()]
prefix_sum = [0]
for a in A:
    prefix_sum.append(prefix_sum[-1] + a)
best = 0
bitset = 1
mask = (1 << nr) - 1
for i in range(nr):
    bitset |= bitset >> i << A[i] + i
    j = highest_set_bit(bitset)
    if j >= nr:
        j = lowest_set_bit(bitset >> nr) + nr
        best = max(best, prefix_sum[-1] - j)
    bitset &= mask
bitset = bin(bitset)[2:][::-1]
for j in range(len(bitset)):
    if bitset[j] == '1':
        best = max(best, prefix_sum[j + 1] - j)
print(best)

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

def highest_set_bit(x):
    return x.bit_length() - 1

def lowest_set_bit(x):
    return highest_set_bit(x ^ x - 1)
n = int(input())
A = [int(x) for x in input().split()]
prefix_sum = [0]
for a in A:
    prefix_sum.append(prefix_sum[-1] + a)
best = 0
bitset = 1
mask = (1 << n) - 1
for i in range(n):
    bitset |= bitset >> i << A[i] + i
    j = highest_set_bit(bitset)
    if j >= n:
        j = lowest_set_bit(bitset >> n) + n
        best = max(best, prefix_sum[-1] - j)
    bitset &= mask
bitset = bin(bitset)[2:][::-1]
for j in range(len(bitset)):
    if bitset[j] == '1':
        best = max(best, prefix_sum[j + 1] - j)
print(best)

Solution (Python):
from sys import stdin

def solve(n, nums):
    ans = 0
    dp = 1
    cur = 0
    mask = (1 << 2 * n) - 1
    for i in range(n):
        dp |= dp >> i << nums[i] + i
        dp &= mask
    dp = bin(dp)[2:][::-1]
    for (i, x) in enumerate(dp):
        if i < n:
            cur += nums[i]
        if x == '1':
            ans = max(ans, cur - i)
    return ans
n = int(input())
nums = list(map(int, stdin.readline()[:-1].split()))
print(solve(n, nums))