JOI 11 本選 Card Game is Fun ( Adhoc )

Card Game is Fun | Aizu Online Judge
Aに対して全てのindexからすぐに次の数字にジャンプできる様にする、O( a ^ 2 )。そうするとBでどこから始めるのか枚挙し、いちいちどこまでいけるかをクエリしてもO( a * b )になる。

#include <bits/stdc++.h>
using namespace std;
const int MAXA = 5000 + 5;
const int MAXB = 5000 + 5;
const int MAXNUM = 1000 + 1;

int n, m;
int a[ MAXA ];
int b[ MAXB ];

int nxt[ MAXA ][ MAXNUM ];

int getMaxlen(int s){
    int cnt = 0;
    int pa = 0; // pointer in a
    for(int i = s; i <= m; ++i){
        pa = nxt[ pa ][ b[ i ] ];
        if( pa == 0 ) break;
        ++cnt;
    }
    return cnt;
}

void solve(){
    for(int i = n; i >= 1; --i)
        for(int j = i - 1; j >= 0; --j){
            nxt[ j ][ a[ i ] ] = i;
            // printf("nxt[ %d ][ %d ] = %d\n", j, a[ i ], i);
        }
    int ans = 0;
    for(int i = 1; i <= m; ++i){ // start from i
        ans = max( ans, getMaxlen( i ) );
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[ i ]);
    for(int i = 1; i <= m; ++i)
        scanf("%d", &b[ i ]);
    solve();
    return 0;
}