This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const ll nx=2505, mod=1e9+7, mul=31;
ll n, a, b, c, s[nx], dp[nx][nx], pw[nx];
string stmp;
struct update
{
ll l, r, cnta, cntc;
update(ll l=0, ll r=0, ll cnta=0, ll cntc=0): l(l), r(r), cnta(cnta), cntc(cntc){}
};
vector<update> calc[nx][nx];
int32_t main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>stmp>>a>>b>>c;
pw[0]=1;
for (int i=1; i<=n; i++) s[i]=stmp[i-1]-'a'+1, pw[i]=(pw[i-1]*mul)%mod;
for (int sz=1; sz<=n; sz++)
{
map<ll, vector<ll>> mp;
ll sm=0;
for (int i=1; i<=sz; i++) sm=(sm+pw[sz-i]*s[i])%mod;
mp[sm].push_back(1);
for (int i=sz+1; i<=n; i++) sm=(sm*mul)%mod, sm=((sm-s[i-sz]*pw[sz])%mod+mod)%mod, sm=(sm+s[i])%mod, mp[sm].push_back(i-sz+1);
for (auto &[_, v]:mp)
{
int csz=v.size(), pts=v.size();
vector<int> pa(csz);
for (int i=csz-1; i>=0; i--)
{
while (pts!=0&&v[i]+sz<=v[pts-1]) pts--;
if (pts!=v.size()) pa[i]=pts;
else pa[i]=-1;
}
/*
cout<<"string update ";
for (int i=v[0]; i<v[0]+sz; i++) cout<<(char)(s[i]-1+'a');
cout<<'\n';
for (int i=0; i<csz; i++) cout<<pa[i]<<' ';
cout<<'\n';*/
for (int i=0; i<csz; i++)
{
if (pa[i]==-1) continue;
ll tmp=pa[i], cnt=2;
while (tmp!=-1)
{
calc[v[0]][v[0]+sz-1].push_back(update(v[i], v[tmp]+sz-1, v[tmp]+sz-v[i]-cnt*sz, cnt));
//cout<<"upd "<<v[i]<<' '<<v[tmp]+sz-1<<' '<<v[tmp]+sz-v[i]-cnt*sz<<' '<<cnt<<'\n';
cnt++;
tmp=pa[tmp];
}
}
}
}
for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dp[i][j]=1e18;
for (int i=1; i<=n; i++) dp[i][i]=a;
for (int sz=0; sz<=n; sz++)
{
for (int l=1; l+sz<=n; l++)
{
int r=l+sz;
if (l!=r) dp[l][r]=min({dp[l][r], dp[l+1][r]+a, dp[l][r-1]+a});
for (auto upd:calc[l][r]) dp[upd.l][upd.r]=min(dp[upd.l][upd.r], dp[l][r]+c*upd.cntc+a*upd.cnta+b);
//cout<<"dp "<<l<<' '<<r<<' '<<dp[l][r]<<'\n';
}
}
cout<<dp[1][n];
}
Compilation message (stderr)
copypaste3.cpp: In function 'int32_t main()':
copypaste3.cpp:40:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | if (pts!=v.size()) pa[i]=pts;
| ~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |