제출 #607516

#제출 시각아이디문제언어결과실행 시간메모리
607516AbdelmagedNourCopy and Paste 3 (JOI22_copypaste3)C++17
100 / 100
742 ms83044 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("Ofast") using namespace std; const long long N=2505,mod=99999999977; long long add(long long a,long long b){ return (a+b)%mod; } long long mul(long long a,long long b){ return (a*b)%mod; } long long dp[N][N],Hash[N][N],nxt[N]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long n,A,B,C; string s; cin>>n>>s>>A>>B>>C; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ Hash[i][j]=add(mul(Hash[i][j-1] ,127),s[j-1]); } } 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 d=0;d<n;d++){ map<long long,int>mp; for(int i=1;i+d<=n;i++){ int j=i+d; dp[i][j]=min({dp[i][j],dp[i+1][j]+A,dp[i][j-1]+A}); } for(int i=n-d;i>=1;i--){ int j=i+d; if(mp[Hash[i][j]])nxt[i]=mp[Hash[i][j]]; else nxt[i]=0; if(j+d<=n)mp[Hash[j][j+d]]=j; } for(int i=1;i+d<=n;i++){ int en=i+d,cnt=1; while(nxt[en-d]){ en=nxt[en-d]+d; cnt++; dp[i][en]=min(dp[i][en],dp[i][i+d]+B+C*cnt+A*(en-i+1 - cnt*(d+1))); } } } 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...