oj.uz

Submission #1010660

# Submission time Handle Problem Language Result Execution time Memory
1010660 2024-06-29T09:17:27 Z ivopav Round words (IZhO13_rowords) C++17
20 / 100
 2000 ms 6208 KB 
#include <bits/stdc++.h>
using namespace std;


int lcs(string a,string b,int n,int m){
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            if (a[i]==b[j]){
                dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1);
            }
            dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            dp[i][j+1]=max(dp[i][j+1],dp[i][j]);
            dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]);
        }
    }
    return dp[n][m];
}

int main(){
    string a;
    string b;
    cin >> a >> b;
    int n=a.size();
    int m=b.size();
    for (int i=0;i<n;i++){
        a.push_back(a[i]);
    }
    for (int i=0;i<m;i++){
        b.push_back(b[i]);
    }
    int najv=0;
    for (int i=0;i<n;i++){
        string c="";
        for (int j=i;j<i+n;j++){
            c+=a[j];
        }
        for (int j=0;j<m;j++){
            string d="";
            for (int k=j;k<j+m;k++){
                d+=b[k];
            }
            najv=max(najv,lcs(c,d,n,m));
        }
    }
    reverse(b.begin(),b.end());
    for (int i=0;i<n;i++){
        string c="";
        for (int j=i;j<i+n;j++){
            c+=a[j];
        }
        for (int j=0;j<m;j++){
            string d="";
            for (int k=j;k<j+m;k++){
                d+=b[k];
            }
            najv=max(najv,lcs(c,d,n,m));
        }
    }
    cout << najv << "\n";
    
}

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 39 ms 348 KB Output is correct
5 Correct 19 ms 344 KB Output is correct
6 Execution timed out 2064 ms 1152 KB Time limit exceeded
7 Execution timed out 2035 ms 4516 KB Time limit exceeded
8 Execution timed out 2055 ms 4508 KB Time limit exceeded
9 Execution timed out 2027 ms 4500 KB Time limit exceeded
10 Execution timed out 2049 ms 4508 KB Time limit exceeded
11 Execution timed out 2029 ms 4948 KB Time limit exceeded
12 Execution timed out 2036 ms 5580 KB Time limit exceeded
13 Execution timed out 2009 ms 5684 KB Time limit exceeded
14 Execution timed out 2023 ms 5124 KB Time limit exceeded
15 Execution timed out 2056 ms 6208 KB Time limit exceeded
16 Execution timed out 2056 ms 5148 KB Time limit exceeded
17 Execution timed out 2033 ms 3852 KB Time limit exceeded
18 Execution timed out 2064 ms 5660 KB Time limit exceeded
19 Execution timed out 2069 ms 4500 KB Time limit exceeded
20 Execution timed out 2078 ms 5404 KB Time limit exceeded
21 Execution timed out 2050 ms 1656 KB Time limit exceeded
22 Execution timed out 2070 ms 2408 KB Time limit exceeded
23 Execution timed out 2021 ms 3188 KB Time limit exceeded
24 Execution timed out 2036 ms 3288 KB Time limit exceeded
25 Execution timed out 2070 ms 4144 KB Time limit exceeded