Codeforces 75D - Big Maximum Sum

問題文 : Big Maximum Sum

解法 :
各配列について
・配列を横断した時の総和
・配列の左から項をとっていったときの最大値
・配列の右から項をとっていったときの最大値
・配列中の要素の最大値

を求めると、求めるべき答えは部分列の連続する項を求める問題(AOJ 0022)のO(n)解法と同じ事をするだけで得ることが出来る.
プログラムの実行時間は、O(n)時間程となる.

コード:

#include <cstdio>
#include <algorithm>

typedef long long ll;

using namespace std;

int main()
{
	int t;
	int n, m;
	ll lMax[50], rMax[50], total[50];
	ll dp[50], dest;
	
	scanf("%d %d", &n, &m);
	
	for (int i = 0; i < n; i++){
		int num;
		scanf("%d", &num);
		
		total[i] = 0;
		lMax[i] = dp[i] = -250000001;
		dest = 0;
		for (int j = 0; j < num; j++){
			scanf("%d", &t);
			total[i] += t;
			lMax[i] = max(total[i], lMax[i]);
			dest += t;
			dp[i] = max(dp[i], dest);
			if (dest < 0) dest = 0;
		}
		rMax[i] = dest;
	}
	
	ll ans = (ll)-250000 * 1000 * 5000 - 1;
	dest = 0;
	for (int i = 0; i < m; i++){
		scanf("%d", &t);
		ans = max(max(ans, dp[t - 1]), max(dest + lMax[t - 1], dest + total[t - 1]));
		dest = max(dest + total[t - 1], rMax[t - 1]);
	}
	
	printf("%lld\n", ans);
	
	return (0);
}