oj.uz

답안 #933641

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933641 2024-02-26T03:45:59 Z mgch 원형 문자열 (IZhO13_rowords) C++14
56 / 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) {
        int curAns = 2;
        for (int j = 0; j < m; ++j) {
            if (ans <= curAns + 2) {
                curAns = lcs(s[i], t[j]);
                if (ans < curAns) {
                    ans = curAns;
                }
            }
            curAns += 2;
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
56.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 600 KB Output isn't correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 37 ms 6240 KB Output is correct
7 Execution timed out 2027 ms 11096 KB Time limit exceeded
8 Incorrect 1439 ms 11312 KB Output isn't correct
9 Correct 1465 ms 11356 KB Output is correct
10 Correct 1351 ms 11348 KB Output is correct
11 Execution timed out 2017 ms 13400 KB Time limit exceeded
12 Execution timed out 2005 ms 13912 KB Time limit exceeded
13 Correct 1942 ms 14084 KB Output is correct
14 Execution timed out 2029 ms 13656 KB Time limit exceeded
15 Execution timed out 2021 ms 14168 KB Time limit exceeded
16 Correct 1869 ms 13616 KB Output is correct
17 Incorrect 1101 ms 15928 KB Output isn't correct
18 Correct 1265 ms 16728 KB Output is correct
19 Correct 1669 ms 11320 KB Output is correct
20 Execution timed out 2033 ms 15960 KB Time limit exceeded
21 Correct 118 ms 11868 KB Output is correct
22 Correct 276 ms 15156 KB Output is correct
23 Correct 191 ms 16364 KB Output is correct
24 Incorrect 572 ms 17348 KB Output isn't correct
25 Incorrect 458 ms 20056 KB Output isn't correct