oj.uz

답안 #933645

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

Subtask #1
32.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 604 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 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 33 ms 6236 KB Output is correct
7 Execution timed out 2061 ms 10844 KB Time limit exceeded
8 Execution timed out 2027 ms 10840 KB Time limit exceeded
9 Execution timed out 2067 ms 10844 KB Time limit exceeded
10 Execution timed out 2065 ms 11100 KB Time limit exceeded
11 Execution timed out 2028 ms 11864 KB Time limit exceeded
12 Execution timed out 2023 ms 13144 KB Time limit exceeded
13 Execution timed out 2068 ms 13148 KB Time limit exceeded
14 Execution timed out 2053 ms 12380 KB Time limit exceeded
15 Execution timed out 2041 ms 13656 KB Time limit exceeded
16 Execution timed out 2033 ms 11864 KB Time limit exceeded
17 Incorrect 1452 ms 12628 KB Output isn't correct
18 Execution timed out 2048 ms 15348 KB Time limit exceeded
19 Execution timed out 2037 ms 10812 KB Time limit exceeded
20 Execution timed out 2017 ms 13656 KB Time limit exceeded
21 Correct 122 ms 11868 KB Output is correct
22 Correct 353 ms 13660 KB Output is correct
23 Correct 682 ms 14400 KB Output is correct
24 Incorrect 724 ms 15384 KB Output isn't correct
25 Incorrect 1252 ms 17284 KB Output isn't correct