| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 567847 | jamezzz | Copy and Paste 3 (JOI22_copypaste3) | C++17 | 0 ms | 0 KiB |
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;
#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));
#define mod 1000000007
#define mod2 1000000009
inline int add(int a,int b){
int r=a+b;
while(r>=mod)r-=mod;
while(r<0)r+=mod;
return r;
}
inline int mult(int a,int b){
return (int)(((ll)(a*b))%mod);
}
inline int rd(){
int x=0;
char ch=getchar_unlocked();
while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
x=(x<<3)+(x<<1)+(ch&15);
ch=getchar_unlocked();
}
return x;
}
int n,a,b,c,cnt;
char s[2505];
int hh[2505][2505],num[2505*2505];
map<ii,int> mp;
vector<ii> v[2505*2505];
vector<int> pos[2505];
ll memo[2505][2505];
unordered_map<int,int> vis[2505][2505];
ll dp(int l,int r){
if(l==r)return a;
if(l+1==r){
if(s[l]!=s[r])return 2*a;
return min(2*a,(ll)a+b+2*c);
}
if(memo[l][r]!=-1)return memo[l][r];
ll ans=(ll)(r-l+1)*a;
for(int i=l;i<=r;++i){
for(int j:pos[i]){
if(j>r/2+1)break;
int x=hh[i][j];
if(vis[l][r][x]!=0)continue;
vis[l][r][x]=1;
int far=l-1,cnt=0;
for(int i=lower_bound(all(v[x]),ii(l,l))-v[x].begin();i<sz(v[x]);++i){
ii pr=v[x][i];
if(pr.se>r)break;
if(far<pr.fi&&pr.se<=r){
++cnt;
far=pr.se;
}
}
if(cnt==1)continue;
ans=min(ans,dp(v[x][0].fi,v[x][0].se)+b+(ll)cnt*c+(ll)(r-l+1-cnt*(j-i+1))*a);
}
}
return memo[l][r]=ans;
}
int main(){
sf("%d",&n);
sf(" %s",&s);
sf("%d%d%d",&a,&b,&c);
for(int i=0;i<n;++i){
ll cur=0,cur2=0;
ll pw=1,pw2=1;
for(int j=i;j<n;++j){
cur+=pw*(s[j]-'a'+1);
cur2+=pw2*(s[j]-'a'+1);
cur%=mod;
cur2%=mod2;
pw*=31;pw%=mod;
pw2*=31;pw2%=mod2;
ii pr=ii((int)cur,(int)cur2);
if(!mp.count(pr)){
mp[pr]=cnt++;
}
hh[i][j]=mp[pr];
v[hh[i][j]].pb({i,j});
}
}
for(int i=n-1;i>=0;--i){
for(int j=i;j<n;++j){
if(num[hh[i][j]]!=0)pos[i].pb(j);
++num[hh[i][j]];
}
}
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
memo[i][j]=LINF;
}
}
pf("%lld\n",dp(0,n-1));
}