Let's sort the array in nonincreasing order. Now the answer is some of the first containers. Let's iterate over array from left to right until the moment when we will have the sum at least m. The number of elements we took is the answer to the problem.

Complexity: $$$\mathcal{O}(nlogn)$$$.

n = int(input())
m = int(input())
flash = []
for _ in range(n):
    val = int(input())
    flash.append(val)
flash.sort(reverse=True)
cur = 0
for i in range(n):
    cur += flash[i]
    if cur >= m:
        print(i + 1)
        break

Note that for each question, the resulting array is

So, the sum of the elements of the new array after each question is

We can compute $$$a_1+⋯+a_{l−1}$$$ and $$$a_{r+1}+⋯+a_n$$$ in $$$\mathcal{O}(1)$$$ time by precomputing the sum of all prefixes and suffixes, or alternatively by using the prefix sums technique. So we can find the sum each time in $$$\mathcal{O}(1)$$$ per question, and just check if it's odd or not. The time complexity is $$$\mathcal{O}(n+q)$$$.

from itertools import accumulate
from sys import stdin


# Fast input for python. Note that it gives you the input with the newline character, '\n'
# This may cause a problem on string problems. In that case, use stdin.readline()[:-1] to strip the last character('\n')
def input(): return stdin.readline()


T = int(input())
for _ in range(T):
    N, Q = map(int, input().split())
    a = list(map(int, input().split()))

    pref_sum = list(accumulate(a, initial=0))

    for __ in range(Q):
        l, r, k = map(int, input().split())
        left_sum = pref_sum[l - 1]
        right_sum = pref_sum[-1] - pref_sum[r]
        middle_sum = k*(r - l + 1)
        total_sum = left_sum + middle_sum + right_sum

        if total_sum%2 == 1:
            print("YES")
        else:
            print("NO")  

The key observation is that to choose an element $$$b_i$$$, we need to consider all elements $$$b_j$$$ where $$$j < i$$$. The objective is to select consecutive elements starting from the first element to maximize the cumulative sum. This principle applies to both the $$$r$$$ and $$$b$$$ sequences.

we can compute the prefix sum for both $$$r$$$ and $$$b$$$. To determine the optimal reconstruction of the original sequence $$$a$$$, we add the maximum prefix sum values from both the $$$r$$$ and $$$b$$$ sequences.

import itertools

t = int(input())

for _ in range(t):
    n = int(input())
    r = list(map(int, input().split()))
    m = int(input())
    b = list(map(int, input().split()))

    r = list(itertools.accumulate(r))
    b = list(itertools.accumulate(b))

    result = max(0, max(r)) + max(0, max(b))
    print(result)

In this problem the sensible thing to do is to count the amount of times we are going to add some index of this sequence; then the maximal number gets assigned to the index that is added the most, and so on. In order to count the amount of times we referenced each index, we can use normal line sweep to store cumulative sums. Finally sort both arrays (the prefix sum array and the main array) and sum the product of the elements on the same index from both arrays.

Time complexity: $$$\mathcal{O}(nlogn)$$$.

Memory complexity: $$$\mathcal{O}(n)$$$.

from itertools import accumulate
from sys import stdin


def input(): return stdin.readline()


N, Q = map(int, input().split())
nums = sorted(map(int, input().split()))

line = [0]*(N + 1)
for _ in range(Q):
    l, r = map(int, input().split())
    line[l - 1] += 1
    line[r] -= 1

counts = sorted(accumulate(line[:-1]))

ans = 0
for i in range(N):
    ans += counts[i]*nums[i]

print(ans)

To determine the order of removals, we start from the end of the string. The last character represents the latest removed character. Moving backward, when encountering a character not seen before, it implies that this character was removed in the next step. Thus, we initiate the process from the last character, and each new character encountered denotes the one removed prior. Once we establish this order, we need to reverse it.

Now that we have the removal order, the next step is to verify whether the resulting string could have originated from that order. To check this, we first need to assess whether the character counts are valid. If a character was removed first, its actual occurrence in the original string should match its count in the given string. If removed second, the real occurrence in the original string is the count in the given string divided by 2, and so on. After obtaining the counts for each character in the original string, if the sum yields a non-integer number, the given string is invalid. However, if it results in an integer, we proceed to check if the given string can be derived from the first $$$k$$$ characters of the original string $$$k$$$ representing the sum of the counts.

To do this, we perform the same operations on the word containing the first $$$k$$$ characters of the given string. After obtaining the result, we compare it with the given string. If they match, we can confidently print the obtained removal order and the original string (which is the first $$$k$$$ characters of the given string). If not, we print $$$-1$$$ as the given string is not valid.

t = int(input())
for _ in range(t):
   s = input()
  
   arr = []
   got = set()
   count = Counter(s)
   for i in s[::-1]:
       if i not in got:
           arr.append(i)
       got.add(i)
   arr.reverse()
   occur = []
   pos = 1
   for i in range(len(arr)):
       occur.append(count[arr[i]] / (i + 1))
   left = 0
   if math.ceil(sum(occur)) != int(sum(occur)):
       pos = 0
 
   if pos:
       ans = ""
       cur = s[:int(sum(occur))]
       j = 0
  
       while cur:
           ans += cur
           stk = ""
           for i in cur:
               if i != arr[j]:
                   stk += i
           cur = stk
           j += 1
       if ans != s:
           pos = 0
   if pos:
       print(s[:int(sum(occur))],"".join(arr))
   else:
       print(-1)