Algorithm

D. Big Maximum Sum
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/75/problem/D
input
standard input
output
standard output

Ahmed and Mostafa used to compete together in many programming contests for several years. Their coach Fegla asked them to solve one challenging problem, of course Ahmed was able to solve it but Mostafa couldn't.

This problem is similar to a standard problem but it has a different format and constraints.

In the standard problem you are given an array of integers, and you have to find one or more consecutive elements in this array where their sum is the maximum possible sum.

But in this problem you are given n small arrays, and you will create one big array from the concatenation of one or more instances of the small arrays (each small array could occur more than once). The big array will be given as an array of indexes (1-based) of the small arrays, and the concatenation should be done in the same order as in this array. Then you should apply the standard problem mentioned above on the resulting big array.

For example let's suppose that the small arrays are {1, 6, -2}, {3, 3} and {-5, 1}. And the indexes in the big array are {2, 3, 1, 3}. So the actual values in the big array after formatting it as concatenation of the small arrays will be {3, 3, -5, 1, 1, 6, -2, -5, 1}. In this example the maximum sum is 9.

Can you help Mostafa solve this problem?

Input

The first line contains two integers n and m, n is the number of the small arrays (1 ≤ n ≤ 50), and m is the number of indexes in the big array (1 ≤ m ≤ 250000). Then follow n lines, the i-th line starts with one integer l which is the size of the i-th array (1 ≤ l ≤ 5000), followed by l integers each one will be greater than or equal -1000 and less than or equal 1000. The last line contains m integers which are the indexes in the big array, and you should concatenate the small arrays in the same order, and each index will be greater than or equal to 1 and less than or equal to n.

The small arrays are numbered from 1 to n in the same order as given in the input. Some of the given small arrays may not be used in big array.

Note, that the array is very big. So if you try to build it straightforwardly, you will probably get time or/and memory limit exceeded.

Output

Print one line containing the maximum sum in the big array after formatting it as described above. You must choose at least one element for the sum, i. e. it cannot be empty.

Please, do not use %lld specificator to write 64-bit integers in C++. It is preferred to use cout (also you may use %I64d).

Examples
input
Copy
3 4
3 1 6 -2
2 3 3
2 -5 1
2 3 1 3
output
Copy
9
input
Copy
6 1
4 0 8 -3 -10
8 3 -2 -5 10 8 -9 -5 -4
1 0
1 -3
3 -8 5 6
2 9 6
1
output
Copy
8



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

enum {
	F = 0, L, R, M
};

int n, m, info[51][4], a[5001], q[250001][4];
long long dp[250001][4];

long long rec(int idx, int stt) {
  if(idx >= m)
    return -2e18;
  
  long long &ret = dp[idx][stt];
  if(ret != -2e18)
    return ret;
  ret = -2e18;

  if(stt == 3) {
  	ret = q[idx][L];
  	ret = max(ret, q[idx][R] + rec(idx + 1, R));
  	ret = max(ret, rec(idx + 1, 3));
  } else if(stt != 1) {
    ret = q[idx][L];
    ret = max(ret, q[idx][F] + rec(idx + 1, F));
  }

  return ret;
}

void calc(int idx, int size) {
  int mxfar = -2e9, mxhere = 0;

  info[idx][L] = info[idx][M] = info[idx][R] = -2e9;

  for(int i = 0, sum = 0; i < size; ++i) {
  	info[idx][F] += a[i];
  	sum += a[i];
  	info[idx][L] = max(info[idx][L], sum);
  }

  for(int i = size - 1, sum = 0; i >= 0; --i) {
  	sum += a[i];
  	info[idx][R] = max(info[idx][R], sum);
  }

  for(int i = 0; i < size; ++i) {
    mxhere += a[i];
    if(mxfar < mxhere) mxfar = mxhere;
    if(mxhere < 0) mxhere = 0;
  }
  
  info[idx][M] = mxfar;
}

int main() {
  scanf("%d %d", &n, &m);
  
  for(int i = 0, tmp; i < n; ++i) {
    scanf("%d", &tmp);
    for(int j = 0; j < tmp; ++j)
      scanf("%d", a + j);
    calc(i, tmp);
  }

  long long mx = -2e9;
  for(int i = 0, tmp; i < m; ++i) {
    scanf("%d", &tmp);
    --tmp;
    for(int j = 0; j < 4; ++j) {
    	q[i][j] = info[tmp][j];
    	mx = max(mx, 1ll * info[tmp][M]);
    }
  }

  for(int i = 0; i < 250001; ++i)
  	for(int j = 0; j < 4; ++j)
  		dp[i][j] = -2e18;
  printf("%lld\n", max(mx, rec(0, 3)));

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
3 4
3 1 6 -2
2 3 3
2 -5 1
2 3 1 3

Output

x
–
+
cmd
9
Advertisements

Demonstration

Codeforcess Solution Big Maximum Sum, D. Big Maximum Sum C,C++, Java, Js and Python ,D. Big Maximum Sum,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+