Codeforces 75D Big Maximum Sum 최대 하위 세그먼트 및 dp

제목 링크: 클릭하여 링크 열기
제목:
첫줄 n m
vector n 개
다음 n줄의 첫 번째 숫자 u는vector의 크기를 표시하고, 다음 u의 숫자는 이vector를 보여 줍니다
마지막 줄 m 숫자
에
큰 서열을 얻어서 이 큰 서열의 최대 자단과
각 벡터의 최대 하위 세그먼트와 왼쪽 연속이 가장 크고 오른쪽 연속이 가장 크며 모든 수의 합을 미리 처리합니다
그리고

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
const long long inf = 1e18;
#define ll long long
#define N 250010
inline ll Max(ll n, ll x[]){
    ll ans = x[0], sum = x[0];
    for(ll i = 1; i < n; i++)
    {
       sum += x[i];
       ans = max(ans, sum);
    }
    return ans;
}

vector<ll>G[N];
ll n, m;
ll l[N],r[N],cop[N],sum[N], w[N];
ll work(ll x){
	ll ans = G[x][0], sum = 0;
	for(ll i = 0; i < G[x].size(); i++)
	{
		if(sum + G[x][i] >= 0){
			sum += G[x][i];
			ans = max(ans, sum);
		}
		else sum = 0;
		ans = max(ans, G[x][i]);
	}
	return ans;
}
void input(){
    for(ll i = 1; i <= n; i++){
        G[i].clear();
		sum[i] = 0;
        ll u, v; scanf("%I64d",&u);
        while(u--)
        {
            scanf("%I64d",&v);
            G[i].push_back(v);
			sum[i] += v;
        }
        for(ll j = 0; j < G[i].size(); j++)cop[j] = G[i][j];
        l[i] = Max((ll)G[i].size(), cop);
        for(ll j = 0; j < G[i].size(); j++)cop[G[i].size()-j-1] = G[i][j];
        r[i] = Max((ll)G[i].size(), cop);
		w[i] = work(i);
    }
}

ll dp[250010][2];
int main() {
    ll u;
    while(~scanf("%I64d %I64d",&n,&m)) {
        input();
        ll ans = -inf;
        dp[0][0] = dp[0][1] = -inf;
        for(ll i = 1; i <= m; i++)
        {
            scanf("%I64d", &u);
            dp[i][0] = dp[i-1][1] + max(sum[u], l[u]);
			dp[i][0] = max(dp[i][0], max(sum[u], l[u]));
			dp[i][1] = dp[i-1][1] + sum[u];
			dp[i][1] = max(dp[i][1], sum[u]);
			dp[i][1] = max(dp[i][1], r[u]);
			ans = max(ans, dp[i][0]);
			ans = max(ans, dp[i][1]);
			ans = max(ans, w[u]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*
3 4
8 -10 1 9 9 -10 2 -10 -9
7 3 -10 -10 -6 3 -7 0
1 -3
1 3 2 3


*/