Submission #872685

#TimeUsernameProblemLanguageResultExecution timeMemory
872685winter0101Copy and Paste 3 (JOI22_copypaste3)C++14
100 / 100
550 ms72856 KiB
#include <bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> const int maxn=2509; int n; string s; long long x,y,z; long long f[maxn][maxn]; int lcp[maxn][maxn]; int id[maxn]; int nxt[maxn]; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); cin>>n>>s>>x>>y>>z; s=" "+s; for1(i,1,n){ for1(j,1,n){ lcp[i][j]=lcp[i-1][j-1]-1; if (lcp[i-1][j-1]==0)lcp[i][j]=0; while (lcp[i][j]<=n-max(j,i)+1&&s[i+lcp[i][j]]==s[j+lcp[i][j]]){ lcp[i][j]++; } } } for1(i,1,n){ for1(j,i,n){ f[i][j]=1ll*(j-i+1)*x; } } for1(len,1,n){ for1(i,1,n-len+1){ id[i]=i; int j=i+len-1; if (i>1)f[i-1][j]=min(f[i-1][j],f[i][j]+x); if (j+1<=n)f[i][j+1]=min(f[i][j+1],f[i][j]+x); } sort(id+1,id+1+n-len+1,[&](int i,int j){ if (lcp[i][j]>=len)return i<j; return s[i+lcp[i][j]]<s[j+lcp[i][j]]; }); for1(i,1,n-len+1)nxt[id[i]]=-1; //if (len==4)for1(i,1,n-len+1)cout<<id[i]<<" "; for1(i,1,n-len+1){ int p=id[i]; int poi=i; for1(j,i,n-len+1){ int q=id[j]; if (lcp[p][q]<len)break; poi=j; } //if (len==1)cout<<i<<" "<<poi<<'\n'; for2(j,poi,i){ int l=j+1,r=poi; //if (len==1)cout<<id[j]<<" "<<j<<" "<<l<<" "<<r<<'\n'; nxt[id[j]]=-1; while (l<=r){ int mid=(l+r)/2; if (id[j]+len<=id[mid]){ nxt[id[j]]=mid; r=mid-1; } else l=mid+1; } //if (len==4&&id[j]==4)cout<<nxt[id[j]]<<'\n'; long long cost=y+z+f[id[j]][id[j]+len-1]; int nw=id[j]; //if (len==1)cout<<id[j]<<" "<<nxt[id[j]]<<'\n'; while (true){ if (nxt[nw]==-1)break; //if (id[j]==1&&len==1)cout<<id[nw]<<" "<<id[nxt[nw]]<<'\n'; int vcl=id[nxt[nw]]; //if (len==4&&id[j]==4)cout<<id[j]<<" "<<nw<<" "<<vcl<<'\n'; cost+=(vcl-1-(nw+len)+1)*x+z; nw=id[nxt[nw]]; f[id[j]][nw+len-1]=min(f[id[j]][nw+len-1],cost); } } i=poi; } } cout<<f[1][n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...