oj.uz

답안 #933644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933644 2024-02-26T03:47:54 Z mgch 원형 문자열 (IZhO13_rowords) C++14
32 / 100
 2000 ms 20056 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], 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);
    }
    for (int i = 0; i < m; ++i) {
        t[i] = b.substr(i) + b.substr(0, i);
    }
    for (int i = 0; i < 1; ++i) {
        for (int j = 0; j < m; ++j) {
            ans = max(ans, lcs(s[i], t[j]));
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
32.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Correct 0 ms 556 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 Execution timed out 2056 ms 11100 KB Time limit exceeded
8 Execution timed out 2017 ms 11096 KB Time limit exceeded
9 Execution timed out 2070 ms 11108 KB Time limit exceeded
10 Execution timed out 2070 ms 11100 KB Time limit exceeded
11 Execution timed out 2028 ms 13404 KB Time limit exceeded
12 Execution timed out 2066 ms 13916 KB Time limit exceeded
13 Execution timed out 2060 ms 13916 KB Time limit exceeded
14 Execution timed out 2063 ms 13660 KB Time limit exceeded
15 Execution timed out 2050 ms 14172 KB Time limit exceeded
16 Execution timed out 2041 ms 13404 KB Time limit exceeded
17 Incorrect 1450 ms 15928 KB Output isn't correct
18 Execution timed out 2052 ms 16476 KB Time limit exceeded
19 Execution timed out 2064 ms 11100 KB Time limit exceeded
20 Execution timed out 2045 ms 15964 KB Time limit exceeded
21 Correct 122 ms 11868 KB Output is correct
22 Correct 354 ms 15160 KB Output is correct
23 Correct 685 ms 16568 KB Output is correct
24 Incorrect 717 ms 17244 KB Output isn't correct
25 Incorrect 1255 ms 20056 KB Output isn't correct