#D0344. 三国

三国

题目背景

这一拜,生死不改,天地日月壮我情怀。——《这一拜》

题目描述

33DAI 在做一道和三国相关的题目,这道题的空间限制为 m MiBm\ \text{MiB}

为了记录三国的地图,他开了 nnint 型多维数组,第 ii 个数组的维度为 rir_i,每个维度的大小分别为 ai,1ai,ria_{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}$

本题中可以认为一个 int4 Byte4\ \text{Byte},一个 long long8 Byte8\ \text{Byte}

输入格式

第一行为空格隔开的两个整数 n,mn,m

接下来 nn 行,第 ii 行首先为一个整数 rir_i,接下来为 rir_i 个整数 ai,1ai,ria_{i,1}\sim a_{i,r_i}

输出格式

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

1 256
1 60000000
Yes

显然 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}$。这就超空间限制了。

1 512
1 60000000
No
3 4096
1 6000
2 3000 3000
3 1000 1000 1000
Yes
3 8796093022208
1 6000
2 3000 3000
3 1000 1000 1000
No

数据规模与约定

  • 对于 30%30\% 的数据,保证 n=1n=1r1=1r_1=1
  • 对于 60%60\% 的数据,保证 ri=1r_i = 1
  • 对于 80%80\% 的数据,保证 m210m\le 2^{10}
  • 对于 100%100\% 的数据,1m2431 \le m \le 2^{43}1n1001\le n\le 1001ai,j2×1091\le a_{i,j} \le 2\times 10^91ri31\le r_i\le 3,保证初始不会超过空间限制。