oj.uz

답안 #1010657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1010657 2024-06-29T09:12:50 Z ivopav 원형 문자열 (IZhO13_rowords) C++17
16 / 100
 139 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;


int lcs(string a,string b,int n,int m){
    vector<vector<vector<vector<int>>>> dp(n+1,vector<vector<vector<int>>>(m+1,vector<vector<int>>(n*2+1,vector<int>(m*2+1,0))));
    int najv=0;
    for (int i=0;i<n;i++){
        for (int j=0;j<m;j++){
            for (int k=i;k<i+n;k++){
                for (int l=j;l<j+n;l++){
           //         cout << i << " " << j << " " << k<< " " << l << "\n";
                    najv=max(najv,dp[i][j][k][l]);
                    if (a[k]==b[l]){
                        dp[i][j][k+1][l+1]=max(dp[i][j][k+1][l+1],dp[i][j][k][l]+1);
                        najv=max(najv,dp[i][j][k+1][l+1]);
                    }
                    dp[i][j][k+1][l]=max(dp[i][j][k+1][l],dp[i][j][k][l]);
                    dp[i][j][k+1][l+1]=max(dp[i][j][k+1][l+1],dp[i][j][k][l]);
                    dp[i][j][k][l+1]=max(dp[i][j][k][l+1],dp[i][j][k][l]);
                    
                }
            }
        }
    }
    return najv;
}

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 rje1=lcs(a,b,n,m);
    reverse(b.begin(),b.end());
    int rje2=lcs(a,b,n,m);
  //  cout << rje1 << " " << rje2 << "\n";
    cout << min(min(n,m),max(rje1,rje2)) << "\n";
    
}

Subtask #1
16.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 8 ms 5008 KB Output is correct
4 Correct 139 ms 119892 KB Output is correct
5 Incorrect 57 ms 47228 KB Output isn't correct
6 Runtime error 51 ms 131072 KB Execution killed with signal 9
7 Runtime error 61 ms 131072 KB Execution killed with signal 9
8 Runtime error 54 ms 131072 KB Execution killed with signal 9
9 Runtime error 59 ms 131072 KB Execution killed with signal 9
10 Runtime error 66 ms 131072 KB Execution killed with signal 9
11 Runtime error 62 ms 131072 KB Execution killed with signal 9
12 Runtime error 66 ms 131072 KB Execution killed with signal 9
13 Runtime error 77 ms 131072 KB Execution killed with signal 9
14 Runtime error 61 ms 131072 KB Execution killed with signal 9
15 Runtime error 64 ms 131072 KB Execution killed with signal 9
16 Runtime error 73 ms 131072 KB Execution killed with signal 9
17 Runtime error 70 ms 131072 KB Execution killed with signal 9
18 Runtime error 70 ms 131072 KB Execution killed with signal 9
19 Runtime error 68 ms 131072 KB Execution killed with signal 9
20 Runtime error 63 ms 131072 KB Execution killed with signal 9
21 Runtime error 55 ms 131072 KB Execution killed with signal 9
22 Runtime error 58 ms 131072 KB Execution killed with signal 9
23 Runtime error 56 ms 131072 KB Execution killed with signal 9
24 Runtime error 61 ms 131072 KB Execution killed with signal 9
25 Runtime error 84 ms 131072 KB Execution killed with signal 9