oj.uz

답안 #1010681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010681 2024-06-29T09:31:03 Z ivopav 원형 문자열 (IZhO13_rowords) C++17
32 / 100
 44 ms 436 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: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
32.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 44 ms 348 KB Output is correct
5 Correct 19 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Incorrect 0 ms 348 KB Output isn't correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Correct 1 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Incorrect 0 ms 436 KB Output isn't correct
17 Incorrect 1 ms 344 KB Output isn't correct
18 Incorrect 1 ms 348 KB Output isn't correct
19 Incorrect 1 ms 348 KB Output isn't correct
20 Incorrect 0 ms 424 KB Output isn't correct
21 Incorrect 1 ms 344 KB Output isn't correct
22 Incorrect 0 ms 348 KB Output isn't correct
23 Incorrect 1 ms 344 KB Output isn't correct
24 Incorrect 1 ms 344 KB Output isn't correct
25 Incorrect 0 ms 344 KB Output isn't correct