oj.uz

답안 #933647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933647 2024-02-26T03:56:04 Z mgch 원형 문자열 (IZhO13_rowords) C++14
48 / 100
 1446 ms 17244 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)4e8) / (n * n); ++jj) {
            int j = all[jj].second;
            ans = max(ans, lcs(s[i], t[j]));
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
48.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 34 ms 6244 KB Output is correct
7 Correct 1229 ms 10992 KB Output is correct
8 Incorrect 1432 ms 10996 KB Output isn't correct
9 Incorrect 1309 ms 10992 KB Output isn't correct
10 Incorrect 1267 ms 10996 KB Output isn't correct
11 Incorrect 1135 ms 12044 KB Output isn't correct
12 Correct 1446 ms 13312 KB Output is correct
13 Incorrect 1149 ms 13304 KB Output isn't correct
14 Incorrect 1103 ms 12484 KB Output isn't correct
15 Incorrect 1116 ms 13908 KB Output isn't correct
16 Correct 1292 ms 11868 KB Output is correct
17 Incorrect 493 ms 12868 KB Output isn't correct
18 Correct 724 ms 15448 KB Output is correct
19 Correct 1247 ms 10992 KB Output is correct
20 Incorrect 864 ms 13660 KB Output isn't correct
21 Correct 112 ms 11868 KB Output is correct
22 Correct 177 ms 13660 KB Output is correct
23 Incorrect 246 ms 14400 KB Output isn't correct
24 Incorrect 231 ms 15196 KB Output isn't correct
25 Incorrect 285 ms 17244 KB Output isn't correct