Submission #1220617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220617		ishaanthenerd	Round words (IZhO13_rowords)	C++20	16 / 100	10 ms	11076 KiB

rowords

#include <bits/stdc++.h>
using namespace std;
using vb = vector<bool>;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;

const ll MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s, t;
    cin >> s >> t;
    int n = s.length(), m = t.length();

    // find start of the longest common subsequence in both words
    vvi dp(n + 1, vi(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp.at(i).at(j) = max(dp.at(i - 1).at(j), dp.at(i).at(j - 1));
            if (s.at(i - 1) == t.at(j - 1)) {
                dp.at(i).at(j) = max(dp.at(i).at(j), dp.at(i - 1).at(j - 1) + 1);
            }
        }
    }
    
    int start_s = n, start_t = m;
    int index_i = n, index_j = m;
    while (index_i > 0 && index_j > 0) {
        if (dp.at(index_i - 1).at(index_j - 1) == dp.at(index_i).at(index_j - 1) && dp.at(index_i - 1).at(index_j - 1) == dp.at(index_i - 1).at(index_j) && dp.at(index_i - 1).at(index_j - 1) + 1 == dp.at(index_i).at(index_j)) {
            index_i--;
            index_j--;
            start_s = index_i;
            start_t = index_j;
        }
        else {
            if (dp.at(index_i - 1).at(index_j) > dp.at(index_i).at(index_j - 1)) {
                index_i--;
            }
            else {
                index_j--;
            }
        }
    }

    // shift so that both starts are the true starts of each word
    s = s.substr(start_s, n - start_s) + s.substr(0, start_s);
    t = t.substr(start_t, m - start_t) + t.substr(0, start_t);

    // recalculate, call it a day
    dp = vvi(n + 1, vi(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp.at(i).at(j) = max(dp.at(i - 1).at(j), dp.at(i).at(j - 1));
            if (s.at(i - 1) == t.at(j - 1)) {
                dp.at(i).at(j) = max(dp.at(i).at(j), dp.at(i - 1).at(j - 1) + 1);
            }
        }
    }
    cout << dp.back().back() << endl;

    return 0;
}

• Subtask 1: 16 / 100