Submission #343315

#	Time	Username	Problem	Language	Result	Execution time	Memory
343315		apostoldaniel854	Round words (IZhO13_rowords)	C++14	100 / 100	50 ms	32876 KiB

rowords

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
using ll = long long;
const int MAX_N = 2000;
int mn[1 + MAX_N][1 + 2 * MAX_N], mx[1 + MAX_N][1 + 2 * MAX_N];
int solve (string a, string b) {
    int n = a.size ();
    int bound = b.size ();
    b = b + b;
    int m = b.size ();
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            mn[i][j] = mx[i][j] = 0;
    for (int j = 0; j <= m; j++)
        mx[0][j] = j;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (a[i - 1] == b[j - 1]) {
                mx[i][j] = mn[i][j - 1];
                mn[i][j] = mx[i - 1][j];
            }
            else {
                mn[i][j] = min (mx[i - 1][j], mn[i][j - 1]);
                mx[i][j] = max (mx[i - 1][j], mn[i][j - 1]);
            }
    int ans = 0;
    for (int i = 1; i <= bound; i++) {
        int cnt = 0;
        for (int j = i; j < i + bound; j++)
            if (mx[n][j] < i)
                cnt++;
        ans = max (ans, cnt);
    }
    return ans;
}
int main () {
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
    string a, b;
    cin >> a >> b;
    int ans = solve (a, b);
    reverse (b.begin (), b.end ());
    ans = max (ans, solve (a, b));
    cout << ans << "\n";
    return 0;
}

• Subtask 1: 100 / 100