English · Original
Chinese · Translation
Formal · Original
*This is the easy version of the problem. The changes in this version are highlighted in bold characters*.
Yugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially there are $0$ edges i.e., there are total $n$ connected components in the graph. He has a freedom to add exactly $k$ undirected edges in this graph, each edge can be added between $u$ and $v$ if and only if $v$ = $u + 1$. Note that he can add multiple edges between two nodes.
After giving this graph to wuhudsm, he will observe the following $m$ requirements and reward him coins :
So Please tell him the optimal way to select these $k$ edges to get maximum number of coins.
Aditionally, help him for $q$ queries.
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.
The first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(2 dot.op 10^3)$, $1 <= m <= bold(2 dot.op 10^3)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.
Next $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).
Next $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.
It is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(2 dot.op 10^3)$.
It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$.
For each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally.
## Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 <= t <= 10^4$). The description of the test cases follows.The first line of test case contains three integers $n, m, q$ ($2 <= n <= bold(2 dot.op 10^3)$, $1 <= m <= bold(2 dot.op 10^3)$, $1 <= q <= 10^6$) — the number of nodes in graph, the number of requirements and the number of queries.Next $m$ lines of each test case contains three space separated integers $x_i, y_i, c_i$ ($1 <= x_i, y_i <= n$, $x_i ≠ y_i$, $1 <= c_i <= 10^9$).Next $q$ lines of each test case contains a single integer $k_i$ ($1 <= k_i <= 10^9$) — the total number of edges needed to add in graph.It is guaranteed that the sum of $n$ and sum of $m$ over all test cases doesn't exceed $bold(2 dot.op 10^3)$.It is guaranteed that the sum of $q$ over all test cases doesn't exceed $10^6$.
## Output
For each test case print $q$ integers — the maximum number of coins he can get if he choose exactly $k_i$ edges optimally.
[samples]
*这是该问题的简单版本。唯一的区别是时间限制和内存限制。*
给定一个大小为 $n$ 的数组 $a$。
你执行以下操作：
记 $s_i = a_{l_i} | a_{l_{i + 1}} | ... | a_{r_i}$。这里 $|$ 表示按位或。
求 $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。
输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。
每个测试用例由多行输入组成。
每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。
接下来的行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。
所有测试用例的 $n$ 之和不超过 $10^6$。
对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。
测试用例 $1$：
选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。
我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。
测试用例 $2$：
选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。
我们得到 $s_1 = 6$。答案是 $s_1 = 6$。
## Input
输入的第一行包含一个整数 $t (1 lt.eq t lt.eq 10^6)$，表示测试用例的数量。每个测试用例由多行输入组成。每个测试用例的第一行包含一个整数 $n (1 lt.eq n lt.eq 10^6)$。接下来的行包含 $n$ 个用空格分隔的整数：$a_1$，$a_2$，...，$a_n$ $(0 lt.eq a_i < 2^{30})$。所有测试用例的 $n$ 之和不超过 $10^6$。
## Output
对于每个测试用例，在新行上输出 —— $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。
[samples]
## Note
测试用例 $1$：选择 $k = 3, [ l_1, r_1 ] = [ 1, 1 ], [ l_2, r_2 ] = [ 2, 2 ], [ l_3, r_3 ] = [ 3, 3 ]$。我们得到 $s_1 = 2, s_2 = 1, s_3 = 2$。答案是 $s_1 - s_2 + s_3 = 2 - 1 + 2 = 3$。测试用例 $2$：选择 $k = 1, [ l_1, r_1 ] = [ 1, 6 ]$。我们得到 $s_1 = 6$。答案是 $s_1 = 6$。
**Definitions**
Let $ t \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $ denote the size of the array.
- Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of non-negative integers, where $ 0 \le a_i < 2^{30} $.
- A *partition* of $ A $ into $ k $ contiguous non-empty subarrays is defined by indices $ 1 = l_1 \le r_1 < l_2 \le r_2 < \dots < l_k \le r_k = n $.
- For each subarray $ [l_i, r_i] $, define $ s_i = \bigvee_{j=l_i}^{r_i} a_j $ (bitwise OR over the subarray).
**Constraints**
1. $ 1 \le t \le 10^6 $
2. $ 1 \le n \le 10^6 $ per test case
3. $ \sum_{\text{all test cases}} n \le 10^6 $
4. $ 0 \le a_i < 2^{30} $ for all $ i $
**Objective**
For each test case, maximize the alternating sum:
$$
\max_{k \ge 1} \sum_{i=1}^{k} (-1)^{i+1} s_i
$$
over all possible partitions of $ A $ into $ k $ contiguous non-empty subarrays.
API Response (JSON)
{
"problem": {
"name": "F1. Award from Wuhudsm(Easy Version)",
"description": {
"content": "*This is the easy version of the problem. The changes in this version are highlighted in bold characters*. Yugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially t",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 7000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CFF1"
},
"statements": [
{
"statement_type": "Markdown",
"content": "*This is the easy version of the problem. The changes in this version are highlighted in bold characters*.\n\nYugandhar have an undirected graph containing $n$ nodes numbered $1, 2,...., n$. Initially t...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "*这是该问题的简单版本。唯一的区别是时间限制和内存限制。*\n\n给定一个大小为 $n$ 的数组 $a$。\n\n你执行以下操作：\n\n记 $s_i = a_{l_i} | a_{l_{i + 1}} | ... | a_{r_i}$。这里 $|$ 表示按位或。\n\n求 $Σ_{i = 1}^k (-1)^{i + 1} * s_i$ 的最大值。\n\n输入的第一行包含一个整数 $t (1 lt.eq t lt....",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ t \\in \\mathbb{Z} $ be the number of test cases. \nFor each test case: \n- Let $ n \\in \\mathbb{Z} $ denote the size of the array. \n- Let $ A = (a_1, a_2, \\dots, a_n) $ be a seq...",
"is_translate": false,
"language": "Formal"
}
]
}