CF75D Big Maximum Sum
题目描述
Ahmed和Mostafa曾经一起竞争在许多编程比赛好几年了。他们的教练Fegla要求他们解决一个具有挑战性的问题,当然Ahmed能够解决它,但是Mostafa不能。
这个问题类似于最大连续子段和问题,但它有不同的格式和约束。
在最大连续子段和问题中,你得到一组整数,你必须在这个数组中找到一个或多个连续的元素,它们的和是最大可能的和。
但在这个问题上,你有n个小数列和一个索引,这个索引里一次包含着小数组的编号,根据这一个索引将小数列串成一个大的数列,每个小数组可能出现不止一次,求大数列的最大连续子段和。例如,假设小数组是{ 1, 6,- 2 },{ 3, 3 }和{ - 5, 1 }。大数组中的索引是{ 2, 3, 1,3 }。因此大数组中的实际值在将它格式化为小数组的串联之后将是{ 3, 3,- 5, 1, 1,6,- 2,- 5, 1 }。在这个例子中,最大和是9。你能帮Mostafa解决这个问题吗?
输入格式
第一行n和m两个整数,分别代表小数列个数和索引长度,接下来的n行,每行开头一个整数l,表示该数列长度,接下来l个整数a[i],分别是小数列的i项。第n+2行,m个整数为索引。
输出格式
一个整数表示最大连续子段和,用长整数形式输出
感谢@dijstra 提供的翻译