Submission #5338305


Source Code Expand

Copy
#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

Submission Time
Task A - わたのはら
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 300
Code Size 989 Byte
Status
Exec Time 159 ms
Memory 98176 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_1.txt, sample_2.txt
Subtask1 300 / 300 sample_1.txt, sample_2.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt, small_5.txt, small_6.txt, small_7.txt, large_1.txt, large_2.txt, large_3.txt, large_4.txt, large_5.txt, large_6.txt, large_7.txt
Case Name Status Exec Time Memory
large_1.txt 36 ms 20992 KB
large_2.txt 52 ms 30976 KB
large_3.txt 59 ms 35584 KB
large_4.txt 80 ms 48256 KB
large_5.txt 47 ms 27776 KB
large_6.txt 108 ms 66048 KB
large_7.txt 159 ms 98176 KB
sample_1.txt 1 ms 256 KB
sample_2.txt 1 ms 256 KB
small_1.txt 1 ms 384 KB
small_2.txt 3 ms 1280 KB
small_3.txt 3 ms 1280 KB
small_4.txt 5 ms 2432 KB
small_5.txt 2 ms 640 KB
small_6.txt 2 ms 768 KB
small_7.txt 2 ms 512 KB