Submission #5338305

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
using namespace std;
template <class T, class U> inline void chmax(T & a, U const & b) { a = max<T>(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

int solve(const string & s, const string & t) {
    int n = s.length();
    vector<vector<int> > dp = vectors(n + 1, n + 1, 0);
    REP (i, n + 1) {
        REP (j, n + 1) {
            if (i - 1 >= 0) chmax(dp[i][j], dp[i - 1][j]);
            if (j - 1 >= 0) chmax(dp[i][j], dp[i][j - 1]);
            if (i - 1 >= 0 and j - 1 >= 0) chmax(dp[i][j], dp[i - 1][j - 1] + (s[i - 1] == t[j - 1]));
        }
    }
    return dp[n][n] + 1;
}

int main() {
    string s, t; cin >> s >> t;
    cout << solve(s, t) << endl;
    return 0;
}

Submission Info

Judge Result