제출 #1010657

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1010657		ivopav	Round words (IZhO13_rowords)	C++17	16 / 100	139 ms	131072 KiB

rowords

#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 / 100