Submission #647326

#	Time	Username	Problem	Language	Result	Execution time	Memory
647326		berr	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	85 / 85	523 ms	283216 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
#define int long long
int sp[3005][3005], ps[3005][3005], p[3005][3005], ss[3005][3005];

void clear()
{
    memset(sp, 0, sizeof(sp));
    memset(ps, 0, sizeof(ps));
    memset(p, 0, sizeof(p));
    memset(ss, 0, sizeof(ss));
 
}

array<int, 3> solve(string s, string t)
{
    clear();

    array<int, 3> ans={0, 0, 0};
 
    int n=s.size(), m=t.size();
 
 
    for(int i=0; i<n; i++)
    for(int l=0; l<m; l++)
    if(s[i]==t[l]) p[i][l]=ss[i][l]=1;
        
    for(int i=1; i<n; i++)
    {
        for(int l=1; l<m; l++)
        {
            if(ss[i][l]) ss[i][l]+=ss[i-1][l-1];
        }
    }
 
    for(int i=n-2; i>=0; i--)
    {
        for(int l=m-2; l>=0; l--)
        {
            if( p[i][l]) p[i][l]+=p[i+1][l+1];
        }
    }
 
 
    for(int i=0; i<n; i++)
    {
        for(int l=0; l<m; l++)
        {
            sp[i][l-ss[i][l]+1]=max(sp[i][l-ss[i][l]+1], ss[i][l]);
            ps[i][l+p[i][l]-1]=max(ps[i][l+p[i][l]-1], p[i][l]);
        }
        
        for(int l=1; l<m; l++)
        {
            sp[i][l]=max(sp[i][l], sp[i][l-1]-1);
        }
        for(int l=m-2; l>=0; l--)
        {
            ps[i][l]=max(ps[i][l], ps[i][l+1]-1);
        }
    }
 
    for(int i=0; i<n-1; i++)
    {
        for(int l=1; l<m; l++)
        {
            if(sp[i][l]+ps[i+1][l-1]>ans[0])
            {
                ans={sp[i][l]+ps[i+1][l-1], i-sp[i][l]+1, l-ps[i+1][l-1]};
            }
        }
    }
 
    return ans;
}
 
 
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
 
 
    string s, t; cin>>s>>t;
 
    array<int, 3> ans=solve(s, t);
    reverse(s.begin(), s.end());
 
    array<int, 3> ans2=solve(s, t);
    
    if(ans2[0]>ans[0])
    {
        ans[0]=ans2[0];
        ans[1]=(s.size()-ans2[1])-ans[0];
        ans[2]=ans2[2];
    }
 
 
    cout<<ans[0]<<"\n"<<ans[1]<<" "<<ans[2];
}

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 40 / 40