问题 6315 --2.三国

6315: 2.三国

题目描述

【题目背景】 这一拜,生死不改,天地日月壮我情怀。——《这一拜》 33DAI 在做一道和三国相关的题目,这道题的空间限制为 $m\ \text{MiB}$。 为了记录三国的地图,他开了 $n$ 个 `int` 型多维数组,第 $i$ 个数组的维度为 $r_i$,每个维度的大小分别为 $a_{i,1}\sim a_{i,r_i}$。 为了避免地图数据超过 `int` 的范围,他决定直接 `#define int long long`,并把主函数的类型改为 `signed`。 33DAI 保证一开始所有数组不会超过题目的空间限制,请问全局把 `int` 改为 `long long` 后会不会超过空间限制。 > $m\ \text{MiB} = m\times 2^{10}\ \text{KiB} = m\times 2^{10}\times 2^{10}\ {Byte}$ > 本题中可以认为一个 `int` 占 $4\ \text{Byte}$,一个 `long long` 占 $8\ \text{Byte}$。

输入

第一行为空格隔开的两个整数 $n,m$。 接下来 $n$ 行,第 $i$ 行首先为一个整数 $r_i$,接下来为 $r_i$ 个整数 $a_{i,1}\sim a_{i,r_i}$。

输出

如果会超出空间限制,输出 `Yes`,否则输出 `No`

样例输入输出

输入#1 复制
1 256
1 60000000
输出#1 复制
Yes
输入#2 复制
1 512
1 60000000
输出#2 复制
No
输入#3 复制
3 4096
1 6000
2 3000 3000
3 1000 1000 1000
输出#3 复制
Yes
输入#4 复制
3 8796093022208
1 6000
2 3000 3000
3 1000 1000 1000
输出#4 复制
No

提示

【样例1解释】 显然 33DAI 定义了一个 `int a[60000000];`,初始占空间大小为 $6\times 10^7\times 4\ \text{Byte}\approx 229\ \text{MiB}$。如果全局把 `int` 改为了 `long long`,空间消耗会变为 $6\times 10^7\times 8 \text{Byte}\approx 458\ \text{MiB}$。这就超空间限制了。 【数据规模与约定】 - 对于 $30\%$ 的数据,保证 $n=1$ 且 $r_1=1$。 - 对于 $60\%$ 的数据,保证 $r_i = 1$。 - 对于 $80\%$ 的数据,保证 $m\le 2^{10}$。 - 对于 $100\%$ 的数据,$1 \le m \le 2^{43}$,$1\le n\le 100$,$1\le a_{i,j} \le 2\times 10^9$,$1\le r_i\le 3$,保证初始不会超过空间限制。
序号 标题 作者 发表时间 费用 订购数 操作