解题思路

本题的核心是在资源约束下最大化注意力信息总量。问题可以分解为以下几个步骤进行求解：

首先需要对所有特征向量进行RMSNorm归一化处理。对于每个d维特征向量，计算其均方根值，然后将向量的每个分量除以该均方根值。这一步保证了后续注意力得分计算的标准化基础。

接着计算所有位置对之间的注意力得分。对于任意两个位置i和j（其中i<j），使用归一化后的向量进行缩放点积运算，得到注意力得分$A_{ij}$，并计算其平方值$A_{ij}^2$。由于最终目标函数中使用的是平方值，因此可以直接存储平方值以便后续使用。

问题的关键在于构造路径矩阵M。对于每个位置j，需要从前面的所有位置中选择最多$c_j$个位置建立连接。为了最大化目标函数S，应当采用贪心策略：对于每个位置j，将所有前置位置按照$A_{ij}^2$的值从大到小排序，然后选择前$c_j$个最大的值。这样可以保证每个位置获得的注意力信息量最大。

题目内容

你正在设计一种跨模态知的大模型精准度机制，给定一个长度为 $n$ 的输入 $token$ 序列，每个位置 $j$ 拥有一个 $d$维特征向量 $X_j \in \mathbb{R}^d$和一个正整数计算容量 $c_j$，表示该位置最多可接收来自前 $j$ 位置的信息连接数。

系统需完成以下步骤：

1. $RMSNorm$ 归一化：对所有特征向量进行 $RMSNorm$ 归一化本题取$(\gamma = 1, \epsilon = 0)$：

   每个特征向量记为$x_i \in \mathbb{R}^d$，其第 $k$ 个分量为 $x_i[k]$。$RMSNorm$ 定义为：

   $\hat{X_i} = \frac{ x_i}{\sqrt{\frac{1}{d}\sum_{k=1}^{d}x_i[k]^2 + \epsilon}}\cdot\gamma$

2. 注意力得分计算：计算每对位置 $i<j$ 的注意力得分，使用标准缩放点积公式（基于 $RMSNorm$ 归一化向量）：

   $A_{ij} = \frac{\hat{x_i} \cdot \hat{x_j}}{\sqrt{d}}$

3. 掩码矩阵构造：构造下三角注意力掩码矩阵$M \in \{0,1\}^{n \times n}$，满足入度约束：

   $\forall j \in [0, n), \sum_{i=0}^{j-1} M_{ij} \leq c_j$

4. 目标函数最大化：最大化全局注意力信息总量，全局注意力信息总量定义为所有激活连接的平方注意力得分之和：

   $S = \sum_{j=0}^{n-1} \sum_{i=0}^{j-1} M_{ij} \cdot A_{ij}^2$

5. 输出整数化得分：最终返回将最大化 $S$ 乘以 $100$ 后四舍五入得到的整数，以实现保留两位小数精度的整数化表示：

   $\text{round}(100 \cdot S)$

输入描述

• 第 $1$ 行: $n$ $d$，以空格分隔，分别表示 $token$ 序列长度和向量维度。
• 接下来 $n$ 行：每行 $d$ 个浮点数，以空格分隔，表示 $x_j$。
• 最后 $1$ 行: $n$ 个正整数，以空格分隔，表示 $c_j$。

约束条件

• $1 \leq n \leq 1000$
• $1 \leq d \leq 100$
• 所有向量非零

输出描述

返回一个整数，即上述步骤 $5$ 的整数化得分

样例1

输入

4 2
2.0 2.0
3.0 0.0
0.0 4.0
1.0 1.0
1 2 1 3

输出

600

说明

位置 $0$：$RMSNorm$ 归一化为 $[1, 1]$；无前置位置$→$对信息总量贡献 $0$

位置 $1$：$RMSNorm$ 归一化为 $[\sqrt{2}, 0]$；前置位置 $j=0$，$A_{01}^2 = 1；c_1 = 2$，选择接收来自 $j=0$ 的信息$→$对信息总量贡献 $1$

位置 $2：RMSNorm$ 归一化为 $[0, \sqrt{2}]$；前置位置 $j=0$ 和 $j=1$，计算 $A_{02}^2=1$,$A_{12}^2 = 0$；$c_2 = 1$，选择接收来自 $j=0$ 的信息$→$对信息总量贡献 $1$

位置 $3：RMSNorm$ 归一化为 $[1, 1]$；前置位置 $j=0$ 和 $j=1$ 和 $j=2$，计算 $A_{03}^2 = 2$，$A_{13}^2 = 1$，$A_{23}^2 = 1$；$c_2 = 3$，选择接收来自 $j=0$ 和 $j=1$ 和 $j=2$ 的信息$→$对信息总量贡献 $4$

最大化 $S=6$，输出整数化得分 $600$

样例2

输入

3 2
1.0 0.0
0.0 1.0
1.0 1.0
1 1 2

输出

200

说明

位置 $0：RMSNorm$ 归一化为 $[\sqrt{2}, 0]$；无前置位置$→$对信息总量贡献 $0$

位置 $1：RMSNorm$ 归一化为 $[0, \sqrt{2}]$；前置位置 $j=0$，$A_{01}^2 = 0$；$c_1 = 1$，选择接收来自 $i=0$ 的信息$→$对信息总量贡献 $0$

位置 $2：RMSNorm$ 归一化为 $[1, 1]$；前置位置 $j=0$ 和 $j=1$，计算 $A_{02}^2 = 1$，$A_{12}^2 = 1$；$c_2 = 2$，选择接收来自 $j=0$ 和 $j=1$ 的信息$→$对信息总量贡献 $2$

最大化 $S=2$，输出整数化得分 $200$