Alice deletes a 0, Bob deletes a 1. Which occurrence should each of them choose?

Deleting a 0 makes the string lexicographically larger. Does the position of that 0 matter?

After Alice's move, Bob sees one string and deletes a 1. What is his best move?

Deleting a 0 at an earlier position is always better for Alice. Indeed, compare deleting the 0s at positions $$$i \lt j$$$: the two results agree before position $$$i$$$, and at position $$$i$$$ the first result has 1 while the second still has 0. So Alice deletes the first 0.

After that, Bob wants to minimize the string. By the symmetric argument he deletes the first 1 of the remaining string, which is the first 1 of the original string, since deleting a 0 never changes the order of the 1s.

Hence the answer is the original string with its first 0 and its first 1 removed.

Complexity: $$$O(n)$$$ per test case.

#include <cstdio>
#include <cstring>
const int N = 105;
char str[N];
void solve() {
    scanf("%s", str + 1);
    int n = strlen(str + 1);
    bool c0 = 0, c1 = 0;
    for (int i = 1; i <= n; i++) {
        if (!c0 && str[i] == '0') {
            c0 = true;
            continue;
        }
        if (!c1 && str[i] == '1') {
            c1 = true;
            continue;
        }
        putchar(str[i]);
    }
    puts("");
}
int main() {
    int t = 0;
    scanf("%d", &t);
    while (t--) solve();
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define nline "\n"
#define sz(x) (int)x.size()

void solve(){
	string s; cin>>s;
	string ans;
	for(int i=0;i<sz(s);i++){
		if(s[i]=='1'){
			continue;
		}
		string t=s;
		t.erase(t.begin()+i);
		string cur;
		for(int j=0;j<sz(t);j++){
			if(t[j]=='0'){
				continue;
			}
			string now=t;
			now.erase(now.begin()+j);
			if((cur.empty()) or (now<cur)){
				cur=now;
			}
		}
		if((ans.empty()) or (ans<cur)){
			ans=cur;
		}
	}
	cout<<ans<<nline;
	return;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll test_cases=1;
	cin>>test_cases;
	while(test_cases--){
		solve();
	}
}

Sort both arrays. Each operation reduces the number of elements by exactly one.

All values are distinct, so no final element can be an untouched original element. What lower bound on $$$n$$$ does this give?

After sorting, in which interval of $$$a$$$ must the $$$i$$$-th smallest value $$$b_i$$$ lie?

Sort both arrays. An operation merges two elements $$$x \le y$$$ into any $$$z \in [x,y]$$$, so think of each final element as the merge of a group of original elements whose min/max bracket its value.

Necessity.

• $$$n \ge 2m$$$. The values in $$$b$$$ are distinct from those in $$$a$$$, so a final element consisting of a single original element is impossible. Every final element needs at least two originals.
• $$$a_i \le b_i \le a_{n-m+i}$$$. The $$$i$$$ smallest final values are produced by $$$i$$$ groups containing at least $$$i$$$ original elements, all $$$\le b_i$$$. Only $$$i-1$$$ original elements are smaller than $$$a_i$$$, so $$$b_i \ge a_i$$$. The symmetric argument on the largest values gives $$$b_i \le a_{n-m+i}$$$.

Sufficiency. If the conditions hold, pair $$$a_i$$$ with $$$a_{n-m+i}$$$ for each $$$i$$$ (the pairs are disjoint since $$$n \ge 2m$$$) and merge each pair into $$$b_i$$$. The remaining middle elements can be attached to any group one by one: merging the current group value $$$b_1$$$ with an extra element $$$e$$$ yields $$$b_1$$$ again, because $$$b_1$$$ lies between them.

Complexity: $$$O((n+m)\log(n+m))$$$ per test case.

using namespace std;

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		int n, m;
		scanf("%d %d", &n, &m);
		vector<int> a(n), b(m);
		for (int &x : a) {
		    scanf("%d", &x);
		}
		for (int &x : b) {
			scanf("%d", &x);
		}
		sort(a.begin(), a.end());
		sort(b.begin(), b.end());

		if (n < 2 * m) {
			puts("NO");
			continue;
		}

		int i = 0;
		while (i < m && a[i] < b[i] && b[i] < a[n - m + i]) ++i;
		puts(i < m ? "no" : "Yes");
	}
	return 0;
}

If a value is chosen when some elements between its two occurrences were already deleted, move its deletion earlier. When is this never worse? Think about $$$(a+b)^2 \ge a^2 + b^2$$$.

Conclude that the process is equivalent to partitioning the array into disjoint blocks: each block is either a single position, or the whole interval between two equal values at its ends.

DP over the prefix. Consider the block containing the last position.

Call an operation full if it deletes the entire original interval between the two occurrences of the chosen value.

Lemma. There is an optimal strategy in which every operation is full.

Suppose a value is chosen with current span $$$p \dots q$$$, while an interval $$$J$$$ strictly inside its original span was deleted earlier. Swap the two deletions: the value now covers the whole original interval. If the two original lengths are $$$A$$$ and $$$B$$$ ($$$A \ge B$$$), the score changes from at most $$$(A-B)^2 + B^2$$$ to $$$A^2$$$, and $$$(A-B)^2 + B^2 \le A^2$$$. So the total never decreases, and repeating this exchange makes every operation full.

Now the deleted intervals are disjoint, and the whole process is exactly: partition the array into blocks, each being a single position or the interval between the two equal values at its ends, and collect $$$\sum (\text{block length})^2$$$.

Let $$$dp[i]$$$ be the best score for the prefix $$$a_1 \dots a_i$$$. The block containing position $$$i$$$ is either the singleton $$${i}$$$, or the interval $$$[l,i]$$$ where $$$l$$$ is the first occurrence of $$$a_i$$$:

The singleton option never overestimates: if the mate of $$$a_i$$$ is still present in the optimal strategy of the prefix, deleting $$$[l,i]$$$ instead is at least as good, since $$$(i-l+1)^2 \ge (i-l)^2 + 1$$$.

The answer is $$$dp[2n]$$$.

Complexity: $$$O(n)$$$ per test case.

#include <bits/stdc++.h>
using namespace std;

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		int n;
		scanf("%d", &n);
		vector<int> a(2 * n);
		for (int &x : a) {
			scanf("%d", &x);
		}

		vector<int> lp(2 * n, -1);
		vector<int> occ(n, -1);
		for (int i = 0; i < 2 * n; ++i) {
			if (occ[a[i] - 1] != -1) {
				lp[i] = occ[a[i] - 1];
			} else {
				occ[a[i] - 1] = i;
			}
		}

		vector<long long> dp(2 * n);
		dp[0] = 1;
		for (int i = 1; i < 2 * n; ++i) {
			dp[i] = dp[i - 1] + 1;
			if (lp[i] != -1) {
				dp[i] = max(dp[i], (lp[i] == 0 ? 0 : dp[lp[i] - 1]) + 1LL * (i - lp[i] + 1) * (i - lp[i] + 1));
			}
		}
		printf("%lld\n", dp[2 * n - 1]);
	}
}

Classify each position by the pair $$$(s_i, t_i)$$$ and count the four types: $$$(0,0)$$$, $$$(0,1)$$$, $$$(1,0)$$$, $$$(1,1)$$$.

Find a quantity that only decreases during the game, and equals $$$0$$$ at the end.

Which pairs of columns can be deleted together in one operation? When can all columns be paired up?

For a substring pair let $$$x=N(0,1)$$$, $$$y=N(1,0)$$$, $$$u=N(0,0)$$$, $$$v=N(1,1)$$$, where $$$N(0,1)$$$ denotes the number occurrences of $$$(0,1)$$$.

Claim. The pair is good iff $$$|x-y| \le u+v$$$.

Necessity: Take any allowed operation. Let the deleted columns have counts $$$u_0, v_0, x_0, y_0$$$ and total $$$k = u_0+v_0+x_0+y_0$$$.

Case $$$c=0$$$:
In the deleted subsequence of $$$s$$$, character $$$0$$$ appears $$$u_0+x_0$$$ times; in $$$t$$$ it appears $$$u_0+y_0$$$ times.
Mode condition:

Adding them: $$$2u_0 + x_0 + y_0 \ge k = u_0+v_0+x_0+y_0$$$ $$$\Rightarrow$$$ $$$u_0 \ge v_0$$$.
Subtracting one from the other gives $$$|x_0 - y_0| \le u_0 - v_0 \le u_0 + v_0$$$.

Case $$$c=1$$$: similarly $$$v_0 \ge u_0$$$ and $$$|x_0 - y_0| \le v_0 - u_0 \le u_0 + v_0$$$.

Thus every operation satisfies $$$|x_0 - y_0| \le u_0+v_0$$$.

Now define the potential $$$\Phi = |x-y| - (u+v)$$$.
After one operation the change is

By the triangle inequality, $$$|x-y| - |(x-y)-(x_0-y_0)| \le |x_0-y_0|$$$.
Therefore

So $$$\Phi$$$ never decreases.
The empty pair has $$$\Phi = 0$$$. Hence initially $$$\Phi \le 0$$$, i.e. $$$|x-y| \le u+v$$$.

Sufficiency: We can empty the strings by repeatedly deleting columns in groups of size 1 or 2.

A single column can be deleted alone iff it is pure: $$$(0,0)$$$ (mode $$$0$$$) or $$$(1,1)$$$ (mode $$$1$$$). Two columns can be deleted together iff they are not two identical mixed columns:

• $$$(0,0)$$$ pairs with anything.

• $$$(1,1)$$$ pairs with anything.

• $$$(0,1)$$$ pairs with $$$(1,0)$$$.

So we can pair $$$\min(x,y)$$$ copies of $$$(0,1)$$$ with $$$(1,0)$$$, and the remaining $$$|x-y|$$$ mixed columns (all of the same type) are paired with pure columns $$$(0,0)$$$ or $$$(1,1)$$$. This is possible exactly because $$$u+v \ge |x-y|$$$.

The leftover $$$u+v-|x-y|$$$ pure columns are paired arbitrarily among themselves. If the total number of columns is odd, exactly one pure column remains and can be deleted alone.

All these pairs / singletons are valid operations. After their deletion the strings become empty, so the pair is good.

Precompute prefix sums for the four column types. For a query $$$[l,r]$$$ obtain the four counts $$$u,v,x,y$$$ in constant time. Answer yes if $$$|x-y| \le u+v$$$, otherwise no.

Complexity: $$$O(n+q)$$$ per test case.

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <iostream>
#include <queue>
typedef long long LL;
using namespace std;
inline int read() {
    int num = 0 ,f = 1; char c = getchar();
    while (!isdigit(c)) f = c == '-' ? -1 : f ,c = getchar();
    while (isdigit(c)) num = (num << 1) + (num << 3) + (c ^ 48) ,c = getchar();
    return num * f;
}
const int N = 2e5 + 5;
char s[N] ,t[N];
int sum[4][N] ,n ,q;
inline void fuling_solve() {
    n = read() ,q = read();
    scanf("%s%s" ,s + 1 ,t + 1);
    for (int j = 0; j < 4; j++) sum[j][0] = 0;
    for (int i = 1; i <= n; i++) {
        int id = (s[i] ^ 48) * 2 + (t[i] ^ 48);
        for (int j = 0; j < 4; j++) sum[j][i] = sum[j][i - 1] + (id == j);
    }
    while (q--) {
        int l = read() ,r = read();
        int a = sum[0][r] - sum[0][l - 1];
        int b = sum[1][r] - sum[1][l - 1];
        int c = sum[2][r] - sum[2][l - 1];
        int d = sum[3][r] - sum[3][l - 1];
        puts(abs(b - c) <= a + d ? "YES" : "NO");
    }
}
signed main() {
    int t = read();
    while (t--) fuling_solve();
    return 0;
}

We have consider to change this problem to a harder version: Find number of pairs $$$(l, r) (1 \le l \le r \le n)$$$ such that $$$(s[l, r], t[l, r])$$$ is good.

Can you solve this too?

Let $$$S_i = F(I(i))$$$. Since the counter resets at $$$n$$$, $$$S_{i+n} = S_i + S_n$$$.

If $$$S_x + S_y \gt S_{x+y+1}$$$ for some $$$x,y$$$, the array $$$I(x),[0],I(y)$$$ already wins. Conversely, if no such pair exists, every array loses.

For fixed $$$y$$$, the function $$$S_x + S_y - S_{x+y+1}$$$ changes only when $$$x+1$$$ or $$$x+y+2$$$ is a reward point. Where is its maximum attained?

Let $$$S_i = F(I(i))$$$ ($$$S_0 = 0$$$). The counter resets exactly at $$$n$$$, so $$$S_{i+n} = S_i + S_n$$$; also $$$F$$$ is additive across a 0: if a string ends with 0, the next part starts from $$$c=0$$$.

Define

Claim. $$$F(s) \le S_{|s|} + \max(M,0)$$$ for every binary array $$$s$$$, with equality for $$$s = I(x),[0],I(y)$$$ at a maximizing pair. Hence the answer is YES iff $$$M \gt 0$$$.

Induct on the number of runs. If $$$s$$$ has no 0, then $$$F(s) = S_{|s|}$$$. Otherwise write $$$s = I(x),[0],t$$$ with $$$x$$$ leading ones. Then

because $$$S_x + S_{|t|} - S_{x+|t|+1} \le M$$$.

Only reward thresholds matter. Let $$$g(x,y) = S_x + S_y - S_{x+y+1}$$$. By periodicity $$$g$$$ is $$$n$$$-periodic in each variable. Fix $$$y$$$:

which is positive only when $$$x+1$$$ is a reward point $$$p_i$$$. On the circle of residues modulo $$$n$$$, the maximum is attained on a plateau whose left end is congruent to some $$$p_i$$$ — so some $$$x = p_i$$$ attains it. The same argument in $$$y$$$ gives

(If $$$m=0$$$, then $$$S_x = dx$$$ and $$$M = -d \le 0$$$.)

Algorithm. All needed values of $$$S$$$ follow from the periodic formula $$$S_i = \lfloor i/n\rfloor S_n + S_{i\bmod n}$$$. For each pair $$$(i,j)$$$, locate $$$p_i+p_j+1$$$ among the sorted points $$${p_1,\dots,p_m, n+p_1,\dots,n+p_m}$$$ with a two-pointer scan; if $$$S_{p_i}+S_{p_j} \gt S_{p_i+p_j+1}$$$ for some pair, print YES.

Complexity: $$$O(m^2)$$$ per test case ($$$\sum m \le 2000$$$).

import sys
input = sys.stdin.readline

class Point:
    def __init__(self, t, v):
        self.t = t
        self.v = v

srw = [Point(0, 0) for _ in range(4100)]

T = int(input())
for _ in range(T):
    n, m, d = map(int, input().split())
    for i in range(1, m+1):
        t, v = map(int, input().split())
        srw[i].t = t
        srw[i].v = v + srw[i-1].v
    for i in range(1, m+1):
        srw[m+i] = Point(n + srw[i].t, srw[m].v + srw[i].v)
    ok = False
    for i in range(1, m+1):
        k = i
        for j in range(1, m+1):
            st = srw[i].t + 1 + srw[j].t
            while k+1 <= 2*m and srw[k+1].t <= st:
                k += 1
            if srw[i].v + srw[i].t*d + srw[j].v + srw[j].t*d > srw[k].v + st*d:
                ok = True
    print("Yes" if ok else "No")
    for i in range(1, 2*m+1):
        srw[i] = Point(0, 0)

Define the deficit $$$g_{x,y} = \text{rowSum}_x + \text{colSum}_y - 3v_{x,y}$$$ of a cell. A cell is a peak iff its deficit is $$$\le 0$$$. How much can one operation reduce a deficit?

For $$$n,m \ge 2$$$, every operation reduces any deficit by at most $$$n+m-3$$$, and full-matrix operations achieve this bound for every cell at once. So the problem reduces to a $$$k$$$-th smallest value.

In one dimension a cell is a peak iff $$$2a_i \ge S$$$ (total sum). Only "full" operations and operations that skip one endpoint matter, and the two endpoint types are never both useful. The rest is a couple of linear inequalities solved in $$$O(1)$$$.

Let $$$R_x = \sum_j v_{x,j}$$$ and $$$C_y = \sum_i v_{i,y}$$$. The peak condition is equivalent to

If an operation covers $$$a$$$ cells of row $$$x$$$ and $$$b$$$ cells of column $$$y$$$, it changes the deficit by $$$-(a+b-3)$$$ when it covers $$$(x,y)$$$, and by $$$-(a+b)$$$ otherwise. For $$$n,m \ge 2$$$ this means the deficit is reduced by at most $$$n+m-3$$$ per operation: full coverage gives $$$a+b-3 \le n+m-3$$$, while an operation avoiding $$$(x,y)$$$ can cover cells of only one of the two lines, contributing at most $$$\max(n-1,m-1) \le n+m-3$$$.

Case $$$n,m \ge 2$$$. After $$$T$$$ operations, cell $$$(x,y)$$$ can be a peak only if $$$g_{x,y} \le T(n+m-3)$$$. Conversely, $$$T$$$ full-matrix operations make every cell with $$$\lceil g_{x,y}/(n+m-3)\rceil \le T$$$ a peak simultaneously. Hence the answer is the $$$k$$$-th smallest value of

Case $$$n=1$$$ or $$$m=1$$$. Rotate to a row of length $$$L=\max(n,m)$$$, sum $$$S$$$.
Peak condition: $$$a_i \ge S-a_i \iff h_i := S-2a_i \le 0$$$.

An operation on a segment of length $$$\ell$$$ subtracts 1 from each element inside.

• If $$$i$$$ is inside: $$$h_i$$$ decreases by $$$\ell-2$$$

• If $$$i$$$ is outside: $$$h_i$$$ decreases by $$$\ell$$$

Only three segment types are useful (others are dominated):

1. Full $$$[1,L]$$$: every $$$h_i$$$ reduced by $$$L-2$$$.

2. Skip‑first $$$[2,L]$$$: $$$h_1$$$ reduced by $$$L-1$$$, others by $$$L-3$$$.

3. Skip‑last $$$[1,L-1]$$$: $$$h_L$$$ reduced by $$$L-1$$$, others by $$$L-3$$$.

Only full operations: Same as the general formula with $$$n+m-3 = L-2$$$:
Answer = $$$k$$$-th smallest $$$\left\lceil \frac{S-2a_i}{L-2} \right\rceil$$$ (with $$$\max(0,\cdot)$$$). (This is exactly the xlim part in the code).

Full + one skip type, with an endpoint among the peaks: Assume the chosen endpoint is $$$p$$$ (either 1 or $$$L$$$), using $$$x$$$ full and $$$y$$$ skip‑$p$ operations ($$$T=x+y$$$). Take the other $$$k-1$$$ peaks as the cells with the largest $$$a_i$$$ (smallest $$$h_i$$$) among the remaining $$$L-1$$$ cells; let $$$v_k$$$ be the smallest of these. Reductions: - For $$$p$$$: $$$(L-2)x + (L-1)y = (L-2)T + y$$$ - For the other $$$k-1$$$ cells: $$$(L-2)x + (L-3)y = (L-2)T - y$$$

Requirements:

From the constraints:

• (2) with $$$y=0$$$ gives $$$T \ge \lceil (S-2v_k)/(L-2) \rceil$$$

• (1) with $$$y=T$$$ gives $$$T \ge \lceil (S-2a_p)/(L-1) \rceil$$$

• Adding (1) and (2): $$$2(L-2)T \ge 2S-2a_p-2v_k \iff T \ge \lceil (S-a_p-v_k)/(L-2) \rceil$$$

Set

(If the first bound $$$\lceil (S-2v_k)/(L-2) \rceil$$$ were strictly larger, then $$$y=0$$$ is optimal and Strategy of only full operations already covers it.)

Now we must check whether there exists an integer $$$y$$$ satisfying the box constraints:

If this holds, $$$T=z$$$ is feasible and optimal for this endpoint; otherwise the endpoint strategy cannot beat the "only full operations" strategy.

The code’s solveL implements exactly this: it computes $$$z$$$, tests feasibility, and returns $$$z$$$ if valid or $$$\infty$$$ otherwise.
The final answer is $$$\min(\text{Strategy full},\; \text{solveL for left endpoint},\; \text{solveL for right endpoint})$$$.

Complexity: $$$O(nm)$$$ per test case.

import math

def ceil_div(a, b):
    return (a + b - 1) // b

def solveL(v, v1, s, k):
    n = len(v) + 1
    if k == 1:
        return max(0, ceil_div(s - 2 * v1, n - 1))
    v.sort(reverse=True)
    vk = v[k - 2]
    z = max(ceil_div(s - v1 - vk, n - 2), ceil_div(s - 2 * v1, n - 1))
    if min(z, (n - 2) * z - s + 2 * vk) >= max(0, s - (n - 2) * z - 2 * v1):
        return z
    return math.inf

T = int(input())
for _ in range(T):
    n, m, k = map(int, input().split())
    s = 0
    u, rs, cs = [], [0] * n, [0] * m
    v = []
    for _ in range(n):
        row = list(map(int, input().split()))
        v.append(row)
        s += sum(row)
        rs[_] = sum(row)
        for j in range(m):
            cs[j] += row[j]
            u.append(row[j])

    if n + m <= 3:
        u.sort()
        if k == 1:
            if n + m == 2 and u[0] < 0:
                print(-1)
            else:
                print(0)
        else:
            print(abs(u[0] - u[1]))
        continue

    xlim = []
    for i in range(n):
        for j in range(m):
            xlim.append(max(0, ceil_div(rs[i] + cs[j] - 3 * v[i][j], n + m - 3)))

    xlim.sort()
    ans = xlim[k - 1]

    if m == 1 or n == 1:
        ans = min(ans, solveL(u[:-1], u[-1], s, k))
        ans = min(ans, solveL(u[1:], u[0], s, k))
    print(ans)

A purchase is a transaction: spend an achievable amount $$$x$$$, gain rebate $$$r(x)$$$, net change $$$r(x)-x$$$. The achievable spends form a knapsack.

Below the smallest spend that yields a net increase, the balance only decreases; reachability is a DP on a DAG.

Above that threshold the balance can grow without bound, and every transaction changes it by a multiple of a single gcd. What determines whether $$$0$$$ is reachable?

If the smallest threshold does not exceed the cheapest product, every purchase is discounted and no positive balance can ever become $$$0$$$.

Let $$$V = \max(s, a_m)$$$ and compute the set $$$C$$$ of spend amounts achievable up to $$$V$$$ with an unbounded knapsack over the prices (a bitset, $$$O(V^2/64)$$$). The rebate for a spend $$$x$$$ is $$$r(x) = \max{b_j : a_j \le x}$$$, obtained by a prefix maximum.

For every achievable $$$x$$$:

• if $$$r(x) \lt x$$$, the net decrease is $$$d = x - r(x)$$$; keep $$$L[d] = \min{x}$$$ — the cheapest way to lose exactly $$$d$$$;
• if $$$r(x) \gt x$$$, the purchase increases the balance; let $$$\text{mnip}$$$ be the smallest such spend.

Below $$$\text{mnip}$$$. Every affordable transaction has $$$r(x) \le x$$$, so the balance only decreases. Define $$$f[0] = 1$$$ and

This is a DAG (all transitions go down); using the minimum spend for each decrease $$$d$$$ is optimal because a cheaper transaction is only more flexible. A shifted bitset computes all $$$f[i]$$$ in $$$O(V^2/64)$$$.

At or above $$$\text{mnip}$$$. A net-increasing purchase is affordable and can be repeated, so the balance can be made arbitrarily large. Every transaction changes the balance by a multiple of

so the residue of the balance modulo $$$g$$$ is invariant, and from a sufficiently large balance every value in the same residue class is reachable (Frobenius). Any path to $$$0$$$ must enter the decreasing region: for the last purchase, $$$b - x + r(x) = 0$$$ with $$$x \le b$$$ forces $$$r(x) = 0$$$ and $$$x = b \lt a_1$$$. Therefore a balance $$$i \ge \text{mnip}$$$ can reach $$$0$$$ iff $$$i \equiv 0 \pmod g$$$ and some positive balance below $$$\text{mnip}$$$ is reachable.

The second condition is automatic when $$$a_1 \gt c_{\min}$$$: the spend $$$c_{\min}$$$ (the cheapest product) has rebate $$$0$$$, so $$$f[c_{\min}] = 1$$$ and $$$c_{\min} \lt \text{mnip}$$$. Conversely, if $$$a_1 \le c_{\min}$$$, every purchase has $$$r(x) \ge b_1 \ge 1$$$, so a purchase of cost $$$x \le h$$$ leaves balance $$$h - x + r(x) \gt 0$$$ — no positive balance can ever become $$$0$$$.

Here $$$I$$$ and $$$D$$$ are the net increases/decreases found above, and the costs and $$$b_m$$$ stand in for the spends beyond $$$V$$$: for $$$x \ge a_m$$$ the net change is $$$x - b_m$$$, and since all achievable spends are multiples of $$$\gcd(c_1,\dots,c_n)$$$, the whole tail contributes exactly $$$\gcd(c_1,\dots,c_n, b_m)$$$.

Complexity: $$$O(V^2/64)$$$ time and $$$O(V)$$$ memory, with $$$V = \max(s, a_m) \le 125\,000$$$.

#include <bits/stdc++.h>
using namespace std;

const int maxV = 125000 + 5;

int Lgcd(const vector<int> &v) {
	return accumulate(v.begin(), v.end(), 0, [](int a, int b) { return gcd(a, b); });
}

int main() {
	int n, m, s;
	scanf("%d %d %d", &n, &m, &s);
	vector<int> c(n);
	vector<pair<int, int>> ab(m);
	for (auto &x : c)
		scanf("%d", &x);
	for (auto &[a, b] : ab)
		scanf("%d %d", &a, &b);
	ab.insert(ab.begin(), make_pair(0, 0));
	m += 1;

	bitset<maxV> p;
	p.set(0);
	for (int x : c)
		p.set(x);

	const int V = max(s, ab.back().first);
	for (int i = 1; i <= V; ++i) {
		if (p[i])
			p |= (p << i);
	}

	vector<int> l(V + 1, s + 1);
	l[0] = 0;
	int mnip = s + 1;
	vector<int> I, D;
	for (int i = 1, abp = 0; i <= V; ++i) {
		if (!p[i])
			continue;
		while (abp + 1 < m && ab[abp + 1].first <= i)
			abp += 1;

		auto [a, b] = ab[abp];
		if (b <= i) {
			l[i - b] = min(l[i - b], i);
			D.push_back(i - b);
		} else {
			I.push_back(b - i);
			mnip = min(mnip, i);
		}
	}

	vector<pair<int, int>> lv;
	for (int i = 1; i <= V; ++i) {
		if (l[i] <= s)
			lv.emplace_back(l[i], i);
	}
	const int ln = lv.size();

	sort(lv.begin(), lv.end());
	sort(c.begin(), c.end());
	sort(I.begin(), I.end());
	sort(D.begin(), D.end());

	bitset<maxV> f, L;
	f.set(0);
	for (int i = 1, lp = 0; i < mnip; ++i) {
		while (lp < ln && lv[lp].first <= i) {
			L.set(maxV - lv[lp].second);
			lp += 1;
		}

		f[i] = ((f & (L >> (maxV - i)))._Find_first() < V);
	}

	int Ig = Lgcd(I), Dg = Lgcd(D), cg = Lgcd(c);
	int ugcd = gcd(gcd(Ig, Dg), gcd(cg, ab.back().second));

	for (int i = 1; i < mnip; ++i)
		puts(f[i] ? "YES" : "NO");
	for (int i = mnip; i <= s; ++i)
		puts((i % ugcd == 0 && ab[1].first > c[0]) ? "YES" : "NO");
	return 0;
}

I promise I'll improve this soon. I know its unclear and skipped some steps for now.