oj.uz

Submission #895599

# Submission time Handle Problem Language Result Execution time Memory
895599 2023-12-30T11:06:34 Z heeheeheehaaw Round words (IZhO13_rowords) C++17
8 / 100
 153 ms 63068 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2392 KB Output isn't correct
4 Incorrect 1 ms 2496 KB Output isn't correct
5 Incorrect 1 ms 2396 KB Output isn't correct
6 Incorrect 57 ms 33384 KB Output isn't correct
7 Correct 23 ms 33372 KB Output is correct
8 Incorrect 52 ms 33364 KB Output isn't correct
9 Incorrect 52 ms 33368 KB Output isn't correct
10 Incorrect 43 ms 33372 KB Output isn't correct
11 Incorrect 49 ms 35420 KB Output isn't correct
12 Incorrect 57 ms 39584 KB Output isn't correct
13 Incorrect 73 ms 39572 KB Output isn't correct
14 Incorrect 56 ms 37464 KB Output isn't correct
15 Incorrect 69 ms 39580 KB Output isn't correct
16 Incorrect 64 ms 35416 KB Output isn't correct
17 Incorrect 95 ms 47960 KB Output isn't correct
18 Incorrect 90 ms 47804 KB Output isn't correct
19 Incorrect 43 ms 33368 KB Output isn't correct
20 Incorrect 97 ms 43684 KB Output isn't correct
21 Incorrect 129 ms 53852 KB Output isn't correct
22 Incorrect 136 ms 57944 KB Output isn't correct
23 Incorrect 145 ms 58080 KB Output isn't correct
24 Incorrect 141 ms 59996 KB Output isn't correct
25 Incorrect 153 ms 63068 KB Output isn't correct