CUBE-192: Memory

#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
int n, m, mx = 0, K;
int A[5010], B[5010];
int mn[5010];
int dp[2][5010];

int main(){

    scanf("%d%d%d", &n, &m, &K);

    for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
    for(int j = 1 ; j <= m; j++) scanf("%d", &B[j]);

    for(int j=1;j<=m;j++) dp[0][j] = mn[j] = j;

    for(int i = 1; i <= n; i++){
        int cur = i % 2, prev = (i-1) % 2;
        dp[cur][0] = 1;
        for(int j = 1; j <= m; j++){
            if(A[i] == B[j]) dp[cur][j] = dp[prev][j-1];
            else dp[cur][j] = INF;
            dp[cur][j] = min(dp[cur][j], 1 + dp[prev][j-1]);
            dp[cur][j] = min(dp[cur][j], 1 + dp[cur][j-1]);
            dp[cur][j] = min(dp[cur][j], 1 + mn[j]);
            if(dp[cur][j] <= K) mx = max(mx, j);
            mn[j] = min(mn[j], dp[cur][j]);
        }
    }

    printf("%d", mx);

    return 0;
}