問題一覧 > 教育的問題

No.3582 Subset Sum Inequalities

レベル : / AI推定難易度 : 2200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 2
作問者 : 👑 p-adic
お気に入りにしたユーザー ProblemId : 9161 / 自分の提出
問題文最終更新日: 2026-10-25 13:18:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 503 (順位表) の他の問題:

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 S and the elements of $S$ in ascending order, separated by single spaces.
  • Line $3$ contains the character T and 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もしくは右上の雲マークをクリックしてアカウントを作成してください。