oj.uz

답안 #933646

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933646 2024-02-26T03:55:40 Z mgch 원형 문자열 (IZhO13_rowords) C++14
40 / 100
 366 ms 17292 KB 
#include <bits/stdc++.h>

using namespace std;

/** so there is complicated algo based on some research let's get it later
 * 
 * 
 *  you have to get that |lcs(a, b) - lcs(a, b[1..n-1] + b[0])| <= 2
 *  so if you have ans >= lcs(a, b) + 2 then ... push it
 * */

const int N = 2024;

int dp[N][N], gr[N], n, m;
string s[N], t[N];

int lcs(const string &a, const string &b) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
            if (a[i] == b[j]) {
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
            }
        }
    }
    return dp[n][m];
}


int main() {
//  freopen("rowords.in", "r", stdin); freopen("rowords.out", "w", stdout);
    string a, b;
    getline(cin, a);
    getline(cin, b);
    n = a.length();
    m = b.length();
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        s[i] = a.substr(i) + a.substr(0, i);
    }
    vector <pair <int, int> > all;
    for (int i = 0; i < m; ++i) {
        t[i] = b.substr(i) + b.substr(0, i);
        for (int j = 0; j < m; ++j) {
            if (gr[i] < n && t[i][j] == a[gr[i]]) {
                ++gr[i];
            }
        }
        all.push_back(make_pair(-gr[i], i));
    }
    sort(all.rbegin(), all.rend());
    for (int i = 0; i < 1; ++i) {
        for (int jj = 0; jj < m && jj < ((int)1e8) / (n * n); ++jj) {
            int j = all[jj].second;
            ans = max(ans, lcs(s[i], t[j]));
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
40.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 34 ms 6236 KB Output is correct
7 Correct 312 ms 10844 KB Output is correct
8 Incorrect 364 ms 11000 KB Output isn't correct
9 Incorrect 335 ms 10992 KB Output isn't correct
10 Incorrect 320 ms 10992 KB Output isn't correct
11 Incorrect 286 ms 12056 KB Output isn't correct
12 Correct 366 ms 13148 KB Output is correct
13 Incorrect 291 ms 13304 KB Output isn't correct
14 Incorrect 278 ms 12380 KB Output isn't correct
15 Incorrect 286 ms 13904 KB Output isn't correct
16 Incorrect 332 ms 12116 KB Output isn't correct
17 Incorrect 127 ms 12632 KB Output isn't correct
18 Correct 193 ms 15376 KB Output is correct
19 Incorrect 321 ms 11000 KB Output isn't correct
20 Incorrect 221 ms 13648 KB Output isn't correct
21 Correct 33 ms 12020 KB Output is correct
22 Correct 49 ms 13664 KB Output is correct
23 Incorrect 66 ms 14172 KB Output isn't correct
24 Incorrect 65 ms 15384 KB Output isn't correct
25 Incorrect 77 ms 17292 KB Output isn't correct