YEZAELP

CUBE-192: Memory

Oct 16th, 2021
507
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int INF = 1e9;
  5. int n, m, mx = 0, K;
  6. int A[5010], B[5010];
  7. int mn[5010];
  8. int dp[2][5010];
  9.  
  10. int main(){
  11.  
  12.     scanf("%d%d%d", &n, &m, &K);
  13.  
  14.     for(int i = 1; i <= n; i++) scanf("%d", &A[i]);
  15.     for(int j = 1 ; j <= m; j++) scanf("%d", &B[j]);
  16.  
  17.     for(int j=1;j<=m;j++) dp[0][j] = mn[j] = j;
  18.  
  19.     for(int i = 1; i <= n; i++){
  20.         int cur = i % 2, prev = (i-1) % 2;
  21.         dp[cur][0] = 1;
  22.         for(int j = 1; j <= m; j++){
  23.             if(A[i] == B[j]) dp[cur][j] = dp[prev][j-1];
  24.             else dp[cur][j] = INF;
  25.             dp[cur][j] = min(dp[cur][j], 1 + dp[prev][j-1]);
  26.             dp[cur][j] = min(dp[cur][j], 1 + dp[cur][j-1]);
  27.             dp[cur][j] = min(dp[cur][j], 1 + mn[j]);
  28.             if(dp[cur][j] <= K) mx = max(mx, j);
  29.             mn[j] = min(mn[j], dp[cur][j]);
  30.         }
  31.     }
  32.  
  33.     printf("%d", mx);
  34.  
  35.     return 0;
  36. }
RAW Paste Data