oj.uz

답안 #475132

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
475132 2021-09-21T09:10:29 Z hackerbhaiya 원형 문자열 (IZhO13_rowords) C++17
20 / 100
 2000 ms 11624 KB 
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimization("unroll-loops")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC optimize("no-stack-protector")
// #define ll __int128
#define ll int
// #define ll int
#define f(i,a,b) for(int i=a;i<b;i++)
#define mod 1000000007
// #define mod 998244353 
#define mp make_pair
#define uniq(v) (v).erase(unique(all(v)),(v).end())
#define ff first
#define ss second
#define rf(i,a,b) for(int i=a;i>=b;i--)
#define sc(a) scanf("%lld",&a)
#define pf printf
#define sz(a) (int)(a.size())
#define psf push_front
#define ppf pop_front
#define ppb pop_back
#define pb push_back
#define pq priority_queue
#define all(s) s.begin(),s.end()
#define sp(a) setprecision(a)
#define rz resize
#define ld long double
#define inf (int)1e9+9
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define eb emplace_back
const double pi = acos(-1);
ll binpow(ll a, ll b){ll res=1;while(b!=0){if(b&1)res*=a;a*=a;b>>=1;}return res;}
// ll binpow(ll a, ll b, ll md){ll res=1;a%=mod;while(b!=0){if(b&1)res*=a,res%=md;a*=a,a%=md;b>>=1;}return res%md;}
 
using namespace std;

ll n,m;
string a,b,s1,s2;
vector<vector<ll> > dp;

ll fn(ll i, ll j, ll mn)
{
    if(i<mn || j<0)
        return 0;
    ll &ans=dp[i][j];
    if(ans==-1)
    {
        ans=0;
        if(a[i]==b[j])
            ans=1+fn(i-1,j-1,mn);
        else
            ans=max(fn(i-1,j,mn),fn(i,j-1,mn));
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("palpath.in","r",stdin);
    // freopen("palpath.out","w",stdout);
    int z=1;
    // cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        ll ans=0;
        cin>>s1>>s2;
        ll len=sz(s1);
        a=s1+s1,b=s2;
        n=sz(a),m=sz(b);
        f(i,0,len)
        {
            dp.clear();
            dp.rz(n,vector<ll> (m,-1));
            ans=max(ans,fn(i+len-1,m-1,i));
        }
        string temp=s1,temp2=s2;
        reverse(all(temp)),reverse(all(temp2));
        a=temp+temp;
        f(i,0,len)
        {
            dp.clear();
            dp.rz(n,vector<ll> (m,-1));
            ans=max(ans,fn(i+len-1,m-1,i));
        }
        b=temp2;
        f(i,0,len)
        {
            dp.clear();
            dp.rz(n,vector<ll> (m,-1));
            ans=max(ans,fn(i+len-1,m-1,i));
        }
        a=s1+s1;
        f(i,0,len)
        {
            dp.clear();
            dp.rz(n,vector<ll> (m,-1));
            ans=max(ans,fn(i+len-1,m-1,i));
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 8 ms 332 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Execution timed out 2094 ms 1284 KB Time limit exceeded
7 Execution timed out 2097 ms 8396 KB Time limit exceeded
8 Execution timed out 2080 ms 8512 KB Time limit exceeded
9 Execution timed out 2097 ms 8496 KB Time limit exceeded
10 Execution timed out 2067 ms 8612 KB Time limit exceeded
11 Execution timed out 2086 ms 9284 KB Time limit exceeded
12 Execution timed out 2074 ms 10892 KB Time limit exceeded
13 Execution timed out 2086 ms 10644 KB Time limit exceeded
14 Execution timed out 2080 ms 9668 KB Time limit exceeded
15 Execution timed out 2084 ms 11624 KB Time limit exceeded
16 Execution timed out 2029 ms 9292 KB Time limit exceeded
17 Execution timed out 2082 ms 7384 KB Time limit exceeded
18 Execution timed out 2073 ms 11024 KB Time limit exceeded
19 Execution timed out 2072 ms 8608 KB Time limit exceeded
20 Execution timed out 2068 ms 9960 KB Time limit exceeded
21 Execution timed out 2083 ms 2772 KB Time limit exceeded
22 Execution timed out 2083 ms 4208 KB Time limit exceeded
23 Execution timed out 2045 ms 5756 KB Time limit exceeded
24 Execution timed out 2069 ms 6240 KB Time limit exceeded
25 Execution timed out 2073 ms 7848 KB Time limit exceeded