Submission #872545

#	Time	Username	Problem	Language	Result	Execution time	Memory
872545		mrwang	Copy and Paste 3 (JOI22_copypaste3)	C++14	100 / 100	1411 ms	325012 KiB

copypaste3

#include<bits/stdc++.h>
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxn=2e5;
const ll inf=1e18;
const ll mod=1e15+37;
ll f[maxn]={0};
ll a,b,c;
vector<pli>g[2506][2506];
void dfs(ll x,ll y,ll h,ll v)
{
    ll j=x+y-1;
    f[j]=min(f[j],-y*h*a+c*h+b+v);
    for(auto zz:g[x][y])
    {
        dfs(zz.fi,zz.se,h+1,v);
    }
}
ll mu(ll a, ll b) {
    ll k = (ll)((long double)a * b / mod);
    ll r = a * b - mod * k;
    if (r < 0) r += mod;
    if (r >= mod) r -= mod;
    return r;
}
string s;
ll hs[maxn],n,pw[maxn];
ll base=311;
ll get(ll i,ll j)
{
    return (hs[j]-mu(hs[i-1],pw[j-i+1]) + mod) %mod;
}
struct qq
{
    ll v,l,r;
    bool operator<(const qq&o)
    {
        if(v==o.v) return l<o.l;
        return v<o.v;
    }
};
ll dp[2506][2506];
vector<qq> vec;
void solve()
{
    cin >> n >> s >> a >> b >> c;
    s=' '+s;
    pw[0]=1;
    for(int i=1;i<=n;i++)
    {
        hs[i]=(hs[i-1]*base+s[i])%mod;
        pw[i]=pw[i-1]*base%mod;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            vec.pb({get(i,j),i,j});
        }
    }
    sort(vec.begin(),vec.end());
    for(int i=0;i<vec.size();i++)
    {
        ll j=i;
        vector<ll> pos;
        while(j<vec.size()&&vec[i].v==vec[j].v)
        {
            pos.pb(vec[j].l);
            j++;
        }
        ll len=vec[i].r-vec[i].l+1;
        for(int q=pos.size()-1;q>=0;q--)
        {
            ll u=pos[q];
            ll x=upper_bound(pos.begin(),pos.end(),u-len)-pos.begin()-1;
            if(x>=0)
            {
                ll v=pos[x];
                g[v][len].pb({u,len});
            }
        }
        i=j-1;
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=i;j<=n;j++)
        {
            if(i==j) dp[i][j]=a;
            else
            {
                dp[i][j]=dp[i][j-1]+a;
                dp[i][j]=min(dp[i][j],(j-i+1)*a+f[j]);
            }
            dfs(i,j-i+1,1,dp[i][j]);
        }
    }
    cout << dp[1][n];
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i=0;i<vec.size();i++)
      |                 ~^~~~~~~~~~~
copypaste3.cpp:71:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<qq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         while(j<vec.size()&&vec[i].v==vec[j].v)
      |               ~^~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 5 / 5
• Subtask 3: 14 / 14
• Subtask 4: 10 / 10
• Subtask 5: 32 / 32
• Subtask 6: 38 / 38