제출 #895599

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895599		heeheeheehaaw	원형 문자열 (IZhO13_rowords)	C++17	8 / 100	153 ms	63068 KiB

rowords

#include <bits/stdc++.h>

using namespace std;

int n, m;
int dp[4005][4005];
int solve(string s1, string s2)
{
    s1 = "#" + s1;
    s2 = "#" + s2;
    int cnt = 1;
    int cn = n, cm = m;
    while(n < m)
        s1.push_back(s2[cnt++]), n++;
    cnt = 1;
    while(m < n)
        s2.push_back(s1[cnt++]), m++;
    for(int i = 0; i <= n + 3; i++)
        for(int j = 0; j <= n + 3; j++)
            dp[i][j] = 0;

    for(int i = 1; i <= n; i++)
    {
        int poz = 0;
        bool ok = false;
        for(int j = i; j >= 1; j--)
            if(s2[j] == s1[i] || s1[j] == s2[i])
                poz = max(poz, j - 1), ok = true;
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j - 1];
            if(ok && (j - (i - poz)) >= 0) dp[i][j] = max(dp[i][j], dp[poz][j - (i - poz)] + 1);
        }
    }

    int rez = 0;
    for(int i = 1; i <= n; i++)
        rez = max(rez, dp[i][n / 2]);
    n = cn;
    m = cm;
    return rez;
}

int main()
{
    string s1, s2;
    cin>>s1>>s2;
    n = (int)s1.size() * 2;
    m = (int)s2.size() * 2;
    int rez = solve((string)(s1 + s1), (string)(s2 + s2));
    reverse(s1.begin(), s1.end());
    rez = max(rez, solve((string)(s1 + s1), (string)(s2 + s2)));
    reverse(s2.begin(), s2.end());
    rez = max(rez, solve((string)(s1 + s1), (string)(s2 + s2)));
    reverse(s1.begin(), s1.end());
    rez = max(rez, solve((string)(s1 + s1), (string)(s2 + s2)));
    cout<<rez<<'\n';
    return 0;
}

• Subtask 1: 8 / 100