题目描述
AcWing 5040. 拼接数组
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010, M = 250010;
typedef long long LL;
int n, m;
LL a[55][N], l[N], r[N], s[N], length[N];
LL b[M], f[M];
LL ans = -N;
bool st[N];
void cal(int idx, int len){
LL sum = 0;
for(int i = 1; i <= len; i ++ ) cin >> a[idx][i], sum += a[idx][i];
s[idx] = sum;
LL ma = -N;
for(int i = 1; i <= len; i ++ ){
f[i] = a[idx][i] + f[i - 1];
ma = max(f[i], ma);
}
r[idx] = ma;
ma = -N;
f[len + 1] = 0;
for(int i = len; i >= 1; i -- ){
f[i] = a[idx][i] + f[i + 1];
ma = max(f[i], ma);
}
l[idx] = ma;
}
void cal2(int idx, int len){
for(int i = 1; i <= len; i ++ ){
if(f[i - 1] <= 0) f[i] = a[idx][i];
else f[i] = f[i - 1] + a[idx][i];
ans = max(ans, f[i]);
}
}
void solve(){
cin >> n >> m;
for(int i = 1; i <= n; i ++ ){
cin >> length[i];
cal(i, length[i]);
//cout << l[i] << ' ' << s[i] << ' ' << r[i] << endl;
}
for(int i = 1; i <= m; i ++ ) cin >> b[i];
for(int i = 1; i <= m; i ++ ){
int v = b[i];
if(f[i - 1] < 0) f[i - 1] = 0;
f[i] = max(f[i - 1] + s[v], l[v]);
ans = max(f[i - 1] + r[v], max(f[i], ans));
st[v] = true;
}
for(int i = 1; i <= n; i ++ )
if(st[i])
cal2(i, length[i]);
cout << ans << endl;
return ;
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
int T = 1;
//cin >> T;
while(T -- ) solve();
return 0;
}