oj.uz

답안 #933648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933648 2024-02-26T03:57:09 Z mgch 원형 문자열 (IZhO13_rowords) C++14
48 / 100
 2000 ms 17492 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);
    if (a.length() < b.length()) {
       swap(a, 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)5e8) / (n * m); ++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 1 ms 768 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 600 KB Output is correct
6 Correct 33 ms 6236 KB Output is correct
7 Correct 1535 ms 11088 KB Output is correct
8 Incorrect 1786 ms 10996 KB Output isn't correct
9 Incorrect 1636 ms 11000 KB Output isn't correct
10 Incorrect 1573 ms 10992 KB Output isn't correct
11 Incorrect 1552 ms 12056 KB Output isn't correct
12 Execution timed out 2019 ms 13312 KB Time limit exceeded
13 Incorrect 1605 ms 13308 KB Output isn't correct
14 Incorrect 1560 ms 12488 KB Output isn't correct
15 Incorrect 1566 ms 13800 KB Output isn't correct
16 Correct 1698 ms 12112 KB Output is correct
17 Incorrect 1454 ms 12632 KB Output isn't correct
18 Correct 1548 ms 15384 KB Output is correct
19 Correct 1551 ms 10996 KB Output is correct
20 Incorrect 1635 ms 13656 KB Output isn't correct
21 Correct 122 ms 11984 KB Output is correct
22 Correct 353 ms 13912 KB Output is correct
23 Correct 681 ms 14172 KB Output is correct
24 Incorrect 721 ms 15384 KB Output isn't correct
25 Incorrect 1263 ms 17492 KB Output isn't correct