oj.uz

Submission #476506

# Submission time Handle Problem Language Result Execution time Memory
476506 2021-09-27T12:19:45 Z hackerbhaiya Round words (IZhO13_rowords) C++14
100 / 100
 110 ms 21964 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 long long
// #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 (ll)1e18
#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;

vector<vector<int> > dp,dir;
string a,b;
int n,m;

void init()
{
    f(i,0,n)
    {
        f(j,0,m)
            dp[i][j]=dir[i][j]=0;
    }
    f(i,1,n)
    {
        f(j,1,m)
        {
            if(a[i]==b[j])
                dp[i][j]=1+dp[i-1][j-1],dir[i][j]=1;
            else
            {
                if(dp[i][j-1]>=dp[i-1][j])
                    dp[i][j]=dp[i][j-1];
                else
                    dp[i][j]=dp[i-1][j],dir[i][j]=2;
            }
        }
    }
}

int cal(int i, int j)
{
    int ans=0;
    while(i>0 && j>0)
    {
        if(dir[i][j]==1)
            ans++,i--,j--;
        else if(dir[i][j]==0)
            j--;
        else
            i--;
    }
    return ans;
}

void update(int id)
{
    int i=id,j=1;
    while(j<m && dir[i][j]!=1)
        j++;
    if(j>=m)
        return;
    dir[i][j]=0;
    while(i<n-1 && j<m-1)
    {
        if(dir[i+1][j]==2)
            i++,dir[i][j]=0;
        else if(dir[i+1][j+1]==1)
            i++,j++,dir[i][j]=0;
        else
            j++;
    }
    while(i<n && j<m)
    {
        if(dir[i+1][j]==2)
            i++,dir[i][j]=0;
        else
            break;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("xortransform.in","r",stdin);
    // freopen("xortransform.out","w",stdout);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif
    int z=1;
    // cin>>z;
    f(i,1,z+1)
    {
        //cout<<"Case #"<<i<<": ";
        cin>>a>>b;
        string tempa=a,tempb=b;
        int dif=sz(tempa);
        a="#"+tempa+tempa,b="$"+tempb;
        n=sz(a),m=sz(b);
        dp.rz(n,vector<int> (m)),dir.rz(n+1,vector<int> (m+1));
        init();
        int ans=cal(dif,m-1),cur=dif+1;
        f(i,2,n)
        {
            if(cur>=n)
                break;
            update(i-1);
            ans=max(ans,cal(cur,m-1)),cur++;
        }
        reverse(all(tempa));
        a="#"+tempa+tempa;
        init();
        ans=max(ans,cal(dif,m-1)),cur=dif+1;
        f(i,2,n)
        {
            if(cur>=n)
                break;
            update(i-1);
            ans=max(ans,cal(cur,m-1)),cur++;
        }
        cout<<ans<<"\n";
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 10 ms 2036 KB Output is correct
7 Correct 31 ms 16076 KB Output is correct
8 Correct 82 ms 16076 KB Output is correct
9 Correct 82 ms 16076 KB Output is correct
10 Correct 68 ms 16132 KB Output is correct
11 Correct 73 ms 17612 KB Output is correct
12 Correct 64 ms 20672 KB Output is correct
13 Correct 110 ms 20648 KB Output is correct
14 Correct 79 ms 18472 KB Output is correct
15 Correct 91 ms 21964 KB Output is correct
16 Correct 89 ms 17772 KB Output is correct
17 Correct 67 ms 13520 KB Output is correct
18 Correct 97 ms 21004 KB Output is correct
19 Correct 61 ms 16076 KB Output is correct
20 Correct 99 ms 18840 KB Output is correct
21 Correct 31 ms 4632 KB Output is correct
22 Correct 50 ms 7700 KB Output is correct
23 Correct 64 ms 10444 KB Output is correct
24 Correct 68 ms 11088 KB Output is correct
25 Correct 90 ms 14780 KB Output is correct