Submission #927810

#	Time	Username	Problem	Language	Result	Execution time	Memory
927810		andrei_boaca	Copy and Paste 3 (JOI22_copypaste3)	C++17	100 / 100	667 ms	48888 KiB

copypaste3

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll INF=1e17;
const ll baza=29,baza2=31;
const ll mod=1e9+7,mod2=998244353;
ll h[2505],A,B,C,h2[2505];
ll dp[2505][2505];
ll v[2505];
pll w[2505];
map<pll,ll> nrm;
vector<int> who[2505];
ll n;
string s;
ll nxt[2505];
ll pw[2505],pw2[2505];
pll gethash(ll l,ll r)
{
    ll rez=(h[r]-(h[l-1]*pw[r-l+1])%mod+mod)%mod;
    ll rez2=(h2[r]-(h2[l-1]*pw2[r-l+1])%mod2+mod2)%mod2;
    return {rez,rez2};
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    pw[0]=1;
    pw2[0]=1;
    for(int i=1;i<=2500;i++)
    {
        pw[i]=(pw[i-1]*baza)%mod;
        pw2[i]=(pw2[i-1]*baza2)%mod2;
    }
    cin>>n>>s>>A>>B>>C;
    s=" "+s;
    for(int i=1;i<=n;i++)
    {
        h[i]=(h[i-1]*baza+s[i]-'a'+1)%mod;
        h2[i]=(h2[i-1]*baza2+s[i]-'a'+1)%mod2;
    }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
            dp[i][j]=INF;
    for(int i=1;i<=n;i++)
        dp[i][i]=A;
    for(int lg=1;lg<n;lg++)
    {
        nrm.clear();
        vector<pll> vals;
        for(ll i=1;i+lg-1<=n;i++)
        {
            w[i]=gethash(i,i+lg-1);
            vals.push_back(w[i]);
        }
        sort(vals.begin(),vals.end());
        vals.erase(unique(vals.begin(),vals.end()),vals.end());
        for(int i=0;i<vals.size();i++)
        {
            nrm[vals[i]]=i+1;
            who[i+1].clear();
        }
        for(int i=1;i+lg-1<=n;i++)
        {
            v[i]=nrm[w[i]];
            who[v[i]].push_back(i);
        }
        for(int i=1;i+lg-1<=n;i++)
        {
            nxt[i]=n+1;
            ll st=0;
            ll dr=who[v[i]].size();
            dr--;
            while(st<=dr)
            {
                int mij=(st+dr)/2;
                if(who[v[i]][mij]>i+lg-1)
                {
                    nxt[i]=who[v[i]][mij];
                    dr=mij-1;
                }
                else
                    st=mij+1;
            }
        }
        for(int i=1;i+lg-1<=n;i++)
        {
            ll l=i;
            ll r=i+lg-1;
            if(l>1)
                dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A);
            if(r<n)
                dp[l][r+1]=min(dp[l][r+1],dp[l][r]+A);
            ll val=dp[l][r];
            ll j=i;
            ll cnt=1;
            while(nxt[j]<=n)
            {
                cnt++;
                j=nxt[j];
                r=j+lg-1;
                ll cost=val+B+C*cnt+A*(r-l+1-cnt*lg);
                dp[l][r]=min(dp[l][r],cost);
            }
        }
    }
    cout<<dp[1][n];
    return 0;
}

Compilation message (stderr)

copypaste3.cpp: In function 'int main()':
copypaste3.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=0;i<vals.size();i++)
      |                     ~^~~~~~~~~~~~

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