oj.uz

Submission #386892

# Submission time Handle Problem Language Result Execution time Memory
386892 2021-04-07T15:30:11 Z two_sides Round words (IZhO13_rowords) C++17
100 / 100
 138 ms 63340 KB 
#include <bits/stdc++.h>

using namespace std;

template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
const int N = 2005;

int dp[N][N * 2], dir[N][N * 2], m, n;
/// 0: up, 1: up-left, 2:left

void init_lcs(string s, string t) {
    memset(dp, 0, sizeof dp);
    memset(dir, 0, sizeof dp);
    m = s.size(), n = t.size(); t += t;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= 2 * n; j++) {
            dp[i][j] = dp[i - 1][j];
            if (s[i - 1] == t[j - 1] && cmax
            (dp[i][j], dp[i - 1][j - 1] + 1))
                dir[i][j] = 1;
            if (cmax(dp[i][j], dp[i][j - 1]))
                dir[i][j] = 2;
        }
}

int get_lcs(int i, int j) {
    int lcs = 0;
    while (i) {
        if (dir[i][j] == 2) j--;
        else if (dir[i][j] == 1) {
            i--; j--; lcs++;
        }
        else i--;
    }
    return lcs;
}

void remove_col(int j) {
    int i = 0;
    while (j < 2 * n) {
        if (dir[i][j + 1] == 2)
            dir[i][++j] = 0;
        else {
            if (i == m) break;
            if (dir[++i][j + 1] == 1)
                dir[i][++j] = 0;
        }
    }
}

int circular_lcs(string s, string t) {
    init_lcs(s, t); int lcs = 0;
    for (int j = 0; j < n; j++) {
        cmax(lcs, get_lcs(m, j + n));
        remove_col(j);
    }
    return lcs;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    string s, t; cin >> s >> t;
    int lcs = circular_lcs(s, t);
    reverse(t.begin(), t.end());
    cout << max(lcs, circular_lcs(s, t));
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 63212 KB Output is correct
2 Correct 50 ms 63212 KB Output is correct
3 Correct 51 ms 63212 KB Output is correct
4 Correct 43 ms 63212 KB Output is correct
5 Correct 44 ms 63212 KB Output is correct
6 Correct 48 ms 63212 KB Output is correct
7 Correct 98 ms 63212 KB Output is correct
8 Correct 113 ms 63340 KB Output is correct
9 Correct 106 ms 63212 KB Output is correct
10 Correct 96 ms 63212 KB Output is correct
11 Correct 104 ms 63212 KB Output is correct
12 Correct 85 ms 63340 KB Output is correct
13 Correct 125 ms 63340 KB Output is correct
14 Correct 113 ms 63212 KB Output is correct
15 Correct 122 ms 63340 KB Output is correct
16 Correct 138 ms 63212 KB Output is correct
17 Correct 88 ms 63340 KB Output is correct
18 Correct 114 ms 63340 KB Output is correct
19 Correct 93 ms 63212 KB Output is correct
20 Correct 120 ms 63340 KB Output is correct
21 Correct 55 ms 63340 KB Output is correct
22 Correct 64 ms 63212 KB Output is correct
23 Correct 77 ms 63212 KB Output is correct
24 Correct 77 ms 63340 KB Output is correct
25 Correct 90 ms 63340 KB Output is correct