Referência para LA 3534 (Luiza)

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

int s[2][10010];
int dp[2][10010];
int l[2];

int find(int snum, int key) {
    int b=0,e=l[snum]-1;

    while (b<=e) {
        int mid = (b+e)/2;

        if (s[snum][mid]==key) return mid;
        else
            if (s[snum][mid]<key) b=mid+1;
            else e=mid-1;
    }

    return -1;
}

int doit(int snum, int spos) {
    if (spos==l[snum]) return 0;
    if (dp[snum][spos]!=-1) return dp[snum][spos];

    int opos = find((snum+1)%2,s[snum][spos]);
    int& res = dp[snum][spos];

    if (opos==-1)
        return res=doit(snum,spos+1)+s[snum][spos];
    else
        return res=s[snum][spos]+max(doit(snum,spos+1),
            doit((snum+1)%2,opos+1));
}

int main() {
    while (1) {
        scanf("%d", &l[0]);
        if (!l[0]) break;
        memset(dp,-1,sizeof(dp));

        for (int i=0; i<l[0]; i++)
            scanf("%d", &s[0][i]);

        scanf("%d", &l[1]);
        for (int i=0; i<l[1]; i++)
            scanf("%d", &s[1][i]);

        printf("%d\n", max(doit(0,0),doit(1,0)));
    }
    return 0;
}