oj.uz

Submission #1010668

# Submission time Handle Problem Language Result Execution time Memory
1010668 2024-06-29T09:25:14 Z ivopav Round words (IZhO13_rowords) C++17
20 / 100
 2000 ms 6036 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;
    if (a.size()*b.size()>-7000){
        vector<int> kola(26,0);
        vector<int> kolb(26,0);
        for (int i=0;i<a.size();i++){
            kola[a[i]-'a']++;
        }
        for (int i=0;i<b.size();i++){
            kolb[b[i]-'a']++;
        }
        int rje=0;
        for (int i=0;i<26;i++){
            rje+=min(kola[i],kolb[i]);
        }
        cout << rje << "\n";
        
        exit(0);
    }
    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";
    
}

Compilation message

rowords.cpp: In function 'int main()':
rowords.cpp:24:26: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     if (a.size()*b.size()>-7000){
      |         ~~~~~~~~~~~~~~~~~^~~~~~
rowords.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i=0;i<a.size();i++){
      |                      ~^~~~~~~~~
rowords.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i=0;i<b.size();i++){
      |                      ~^~~~~~~~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 38 ms 348 KB Output is correct
5 Correct 17 ms 448 KB Output is correct
6 Execution timed out 2098 ms 872 KB Time limit exceeded
7 Execution timed out 2049 ms 4532 KB Time limit exceeded
8 Execution timed out 2059 ms 4636 KB Time limit exceeded
9 Execution timed out 2037 ms 4488 KB Time limit exceeded
10 Execution timed out 2031 ms 4488 KB Time limit exceeded
11 Execution timed out 2017 ms 4896 KB Time limit exceeded
12 Execution timed out 2037 ms 5652 KB Time limit exceeded
13 Execution timed out 2033 ms 5604 KB Time limit exceeded
14 Execution timed out 2051 ms 5180 KB Time limit exceeded
15 Execution timed out 2052 ms 6036 KB Time limit exceeded
16 Execution timed out 2029 ms 5072 KB Time limit exceeded
17 Execution timed out 2054 ms 3856 KB Time limit exceeded
18 Execution timed out 2061 ms 5856 KB Time limit exceeded
19 Execution timed out 2032 ms 4544 KB Time limit exceeded
20 Execution timed out 2028 ms 5172 KB Time limit exceeded
21 Execution timed out 2045 ms 1544 KB Time limit exceeded
22 Execution timed out 2032 ms 2576 KB Time limit exceeded
23 Execution timed out 2058 ms 3112 KB Time limit exceeded
24 Execution timed out 2058 ms 3280 KB Time limit exceeded
25 Execution timed out 2041 ms 4180 KB Time limit exceeded