Submission #548738

#TimeUsernameProblemLanguageResultExecution timeMemory
548738luka1234Copy and Paste 3 (JOI22_copypaste3)C++14
25 / 100
3078 ms20692 KiB
#include <bits/stdc++.h> #define ll long long #define ff first #define ss second using namespace std; ll n,A,B,C; string s="#"; string s1; ll xar[2501]; ll hs[2501]; ll num[501]; ll pir[501]; ll dp[2501][2501]; ll p=1000000007; void makehash(string s){ xar[0]=1; ll cd; for(int k=1;k<=n;k++){ xar[k]=xar[k-1]*31; xar[k]%=p; } hs[0]=0; for(int k=1;k<=n;k++){ hs[k]=hs[k-1]*31; hs[k]%=p; cd=s[k]-'a'; hs[k]+=cd; hs[k]%=p; } } ll gethash(int l,int r){ ll ans; ll raodenoba=r-l+1; ll r1=hs[r]; ll r2=hs[l-1]*xar[raodenoba]; r1%=p; r2%=p; ans=r2-r1; ans+=p; ans%=p; return ans; } int main(){ /*ios_base::sync_with_stdio(0); cin.tie(0);*/ cin>>n; cin>>s1; s+=s1; cin>>A>>B>>C; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ dp[i][j]=1e18; } } fill(pir,pir+n+1,1e18); ll len=0; ll newlen=0; ll ric1=0,ric2=0; makehash(s); for(int r=1;r<=n;r++){ fill(pir,pir+r+1,1e18); fill(num,num+r+1,0); for(int l=r;l>=1;l--){ dp[l][r]=min(dp[l][r],dp[l][r-1]+A); for(int i=l;i<=r;i++){ len=i-l+1; ric1=gethash(l,i); ric2=gethash(r-len+1,r); if(ric1==ric2&&i<pir[len]){ pir[len]=l; num[len]++; } newlen=(C-len*A)*num[len]+(r-l+1)*A+dp[r-len+1][r]+B; dp[l][r]=min(dp[l][r],newlen); } } } cout<<dp[1][n]; return 0; }
#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...