oj.uz

Submission #800562

# Submission time Handle Problem Language Result Execution time Memory
800562 2023-08-01T16:12:16 Z fatherofnation Round words (IZhO13_rowords) C++14
24 / 100
 2000 ms 8400 KB 
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int longestCommonSubsequence(const string& word1, const string& word2) {
    int m = word1.length();
    int n = word2.length();

    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

vector<string> findRoundWords(const string& word) {
    int n = word.length();
    vector<string> roundWords;

    for (int i = 0; i < n; ++i) {
        string rotatedWord = word.substr(i) + word.substr(0, i);
        roundWords.push_back(rotatedWord);
    }

    return roundWords;
}

int main() {
    string word1, word2;
    cin >> word1 >> word2;

    vector<string> roundWords = findRoundWords(word1);

    int maxLCS = 0;
    for (const string& roundWord : roundWords) {
        int lcs = longestCommonSubsequence(roundWord, word2);
        maxLCS = max(maxLCS, lcs);
    }

    cout << maxLCS << endl;

    return 0;
}

Subtask #1
24.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 250 ms 1940 KB Output is correct
7 Execution timed out 2051 ms 5428 KB Time limit exceeded
8 Execution timed out 2074 ms 5472 KB Time limit exceeded
9 Execution timed out 2064 ms 5456 KB Time limit exceeded
10 Execution timed out 2066 ms 5432 KB Time limit exceeded
11 Execution timed out 2059 ms 6028 KB Time limit exceeded
12 Execution timed out 2047 ms 7136 KB Time limit exceeded
13 Execution timed out 2074 ms 6960 KB Time limit exceeded
14 Execution timed out 2067 ms 6420 KB Time limit exceeded
15 Execution timed out 2086 ms 7484 KB Time limit exceeded
16 Execution timed out 2083 ms 6000 KB Time limit exceeded
17 Execution timed out 2075 ms 5840 KB Time limit exceeded
18 Execution timed out 2070 ms 8084 KB Time limit exceeded
19 Execution timed out 2080 ms 5536 KB Time limit exceeded
20 Execution timed out 2089 ms 6880 KB Time limit exceeded
21 Correct 1312 ms 4668 KB Output is correct
22 Execution timed out 2082 ms 5636 KB Time limit exceeded
23 Execution timed out 2080 ms 6384 KB Time limit exceeded
24 Execution timed out 2045 ms 6752 KB Time limit exceeded
25 Execution timed out 2074 ms 8400 KB Time limit exceeded