oj.uz

Submission #933673

# Submission time Handle Problem Language Result Execution time Memory
933673 2024-02-26T04:39:58 Z mgch Round words (IZhO13_rowords) C++14
64 / 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 = 1;
        for (int j = 0; j < m; ++j) {
            if (ans <= curAns + 1) {
                curAns = lcs(s[i], t[j]);
                if (ans < curAns) {
                    ans = curAns;
                }
            }
            curAns += 1;
        }
    }
    cout << ans << '\n';
    return 0;
}

Subtask #1
64.0 / 100.0

# Verdict Execution time Memory 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 2065 ms 11100 KB Time limit exceeded
8 Incorrect 793 ms 11312 KB Output isn't correct
9 Correct 899 ms 11308 KB Output is correct
10 Correct 759 ms 11316 KB Output is correct
11 Correct 1359 ms 13620 KB Output is correct
12 Execution timed out 2052 ms 13916 KB Time limit exceeded
13 Correct 1290 ms 14084 KB Output is correct
14 Correct 1639 ms 13736 KB Output is correct
15 Execution timed out 2008 ms 14168 KB Time limit exceeded
16 Correct 1245 ms 13612 KB Output is correct
17 Incorrect 779 ms 15708 KB Output isn't correct
18 Correct 791 ms 16636 KB Output is correct
19 Correct 1283 ms 11316 KB Output is correct
20 Incorrect 1318 ms 16216 KB Output isn't correct
21 Correct 98 ms 11976 KB Output is correct
22 Correct 215 ms 15156 KB Output is correct
23 Correct 135 ms 16220 KB Output is correct
24 Incorrect 400 ms 17348 KB Output isn't correct
25 Incorrect 257 ms 20056 KB Output isn't correct