[HOJ] 332 - 交換數列

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
struct P{
    int val,in;
}s[500005];
int cmp(P a,P b){
    return a.val<b.val;
}
vector<long long int> arr,vec[500005];
long long int dp[1000005]={0},L=0;
bool is[1000005]={0};
int main(){
    int n,m,l=0,x,i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&m);
        if(is[m]==0){
            is[m]=1;
            arr.push_back(m);
        }
        l=max(l,m);
        s[i].val=m,s[i].in=i;
        vec[i].push_back(0);
        for(j=0;j<m;j++){
            scanf("%d",&x);
            long long int pre=0;
            pre=vec[i][j];
            vec[i].push_back(pre+x);
        }
    }
    arr.push_back(0);
    sort(arr.begin(),arr.end());
    sort(s,s+n,cmp);
    for(i=1;i<=l;i++)
        dp[i]=-100000000000000001LL;
    long long int ans=-100000000000000001LL;
    for(i=1;i<arr.size();i++){
        int r=arr[i],l=arr[i-1];
        while(L<n && s[L].val<r) L++;
        if(L==n) break;
        for(j=L;j<n;j++){
            dp[r]=max(dp[r],dp[l]+vec[s[j].in][r]-vec[s[j].in][l]);
        }
        ans=max(ans,dp[r]);
    }
    printf("%lld\n",ans);
}