Submission #47552

#	Time	Username	Problem	Language	Result	Execution time	Memory
47552		ngkan146	Round words (IZhO13_rowords)	C++11	36 / 100	80 ms	32784 KiB

rowords

#include <bits/stdc++.h>
using namespace std;
string t[2], s[2];
int dp[4005][4005];
int lca(string &a, string &b){
    for(int i=1;i<a.size();i++){
        for(int j=1;j<b.size();j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if (a[i] == b[j])
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
        }
    }
    return dp[a.size()-1][b.size()-1];
}
int main(){
    cin >> t[0] >> t[1];
    s[0] = '0' + t[0];
    s[1] = '0' + t[1];

    int tmp = lca(s[0], s[1]);
    s[0] = '0' + t[0] + t[0];
    s[1] = '0' + t[1] + t[1];
    tmp = lca(s[0], s[1]) - tmp;

    reverse(t[0].begin(), t[0].end());

    s[0] = '0' + t[0];
    s[1] = '0' + t[1];

    int tmp2 = lca(s[0], s[1]);
    s[0] = '0' + t[0] + t[0];
    s[1] = '0' + t[1] + t[1];
    tmp2 = lca(s[0], s[1]) - tmp2;
    cout << max(tmp, tmp2);
}

Compilation message (stderr)

rowords.cpp: In function 'int lca(std::__cxx11::string&, std::__cxx11::string&)':
rowords.cpp:6:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<a.size();i++){
                 ~^~~~~~~~~
rowords.cpp:7:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=1;j<b.size();j++){
                     ~^~~~~~~~~

• Subtask 1: 36 / 100