No.3582 Subset Sum Inequalities
タグ : / 解いたユーザー数 2
作問者 : 👑
Problem Statement
First, $2$ positive integers $N, Q$ are given.
A set $X$ is given, which is initially the empty set.
Update $X$ by processing the $Q$ queries described below in the given order, and determine whether the condition "every $N$-dimensional integer vector belongs to $X$" holds at the point when all queries have been processed.
Each query is a tuple $(A,B,M,S,T)$ of $2$ non-negative integers $A, B$ not greater than $N$, an integer $M$, a set $S$ with $A$ elements consisting only of positive integers not greater than $N$, and a set $T$ with $B$ elements consisting only of positive integers not greater than $N$.
To process a query $(A,B,M,S,T)$, update $X$ by inserting into $X$ every $N$-dimensional integer vector $x$ satisfying the condition $\sum_{i \in S} x_i \leq M + \sum_{j \in T} x_j$.
Here, for an $N$-dimensional integer vector $x$ and a positive integer $i$ not greater than $N$, $x_i$ denotes the $i$-th component of $x$.
Input
The input is given from standard input in $3Q+1$ lines in the following format:
- Line $1$ contains $N,Q$ separated by single spaces.
- For each positive integer $q$ not greater than $Q$, the $q$-th query is given in $3$ lines, from line $3q - 1$ to line $3q + 1$.
$N$ $Q$ ($1$ 個目のクエリ) $\vdots$ ($Q$ 個目のクエリ)
Each query $(A,B,M,S,T)$ is given in $3$ lines in the following format:
- Line $1$ contains $A,B,M$ separated by single spaces.
- Line $2$ contains the character
Sand the elements of $S$ in ascending order, separated by single spaces. - Line $3$ contains the character
Tand the elements of $T$ in ascending order, separated by single spaces.
$A$ $B$ $M$ S $S$ T $T$
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^3$
- $Q$ is an integer satisfying $1 \leq Q \leq 10^3$
- For any positive integer $q$ not greater than $Q$, the $q$-th query $(A,B,M,S,T)$ satisfies the following:
- $A$ is an integer satisfying $0 \leq A \leq N$
- $B$ is an integer satisfying $0 \leq B \leq N$
- $M$ is an integer satisfying $- 10^{9} \leq M \leq 10^{9}$
- $S$ is a set with $A$ elements consisting only of positive integers not greater than $N$
- $T$ is a set with $B$ elements consisting only of positive integers not greater than $N$
- For any positive integer $i$ not greater than $N$, the sum of the following $2$ numbers is at most $2$:
- The number of queries $(A,B,M,S,T)$ satisfying $i \in S$
- The number of queries $(A,B,M,S,T)$ satisfying $i \in T$
Output
Print Yes if the condition "every $N$-dimensional integer vector belongs to $X$" holds at the point when all queries have been processed, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
1 1 1 0 1 S 1 T
Output
No
The $1$-st query $(1,0,1,\{1\},\{\})$ replaces $X$, from the empty set $\{\}$, with
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{1\}} x_i \leq 1 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 1\}$
For example, the $N = 1$-dimensional integer vector $(2)$ does not belong to $X$.
Sample 2
Input
1 2 1 0 0 S 1 T 0 1 1 S T 1
Output
Yes
The $1$-st query $(1,0,0,\{1\},\{\})$ replaces $X$, from the empty set $\{\}$, with
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{1\}} x_i \leq 0 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 0\} $
Furthermore, the $2$-nd query $(0,1,1,\{\},\{1\})$ replaces $X$ with
$\displaystyle \{x \in \mathbb{Z}^1 \mid x_1 \leq 0\} \cup \left\{x \in \mathbb{Z}^1 \middle| \sum_{i \in \{\}}^{1} x_i \leq 1 + \sum_{j \in \{1\}} x_j \right\} = \{x \in \mathbb{Z}^1 \mid x_1 \leq 0 \lor 0 \leq 1 + x_1\} = \mathbb{Z}^1 $
In particular, every $N = 1$-dimensional integer vector belongs to $X$.
Sample 3
Input
2 2 0 2 2 S T 1 2 2 0 -1 S 1 2 T
Output
Yes
The $1$-st query $(0,2,2,\{\},\{1,2\})$ replaces $X$, from the empty set $\{\}$, with
$\displaystyle \{\} \cup \left\{x \in \mathbb{Z}^2 \middle| \sum_{i \in \{\}} x_i \leq 2 + \sum_{j \in \{1,2\}} x_j \right\} = \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2\} $
Furthermore, the $2$-nd query $(2,0,-1,\{1,2\},\{\})$ replaces $X$ with
$\displaystyle \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2\} \cup \left\{x \in \mathbb{Z}^2 \middle| \sum_{i \in \{1,2\}} x_i \leq -1 + \sum_{j \in \{\}} x_j \right\} = \{x \in \mathbb{Z}^2 \mid 0 \leq 2 + x_1 + x_2 \lor x_1 + x_2 \leq -1\} = \mathbb{Z}^2 $
In particular, every $N = 2$-dimensional integer vector belongs to $X$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。