Submission #972565

#TimeUsernameProblemLanguageResultExecution timeMemory
972565happy_nodeCopy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
3089 ms48256 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MX=2505; int N, A, B, C; string s; ll dp[MX][MX]; ll ndp[MX]; bool ok(int a, int b, int l, int r) { if(l<=b) return false; for(int k=0;k<b-a+1;k++) { if(s[a+k]!=s[l+k]) return false; } return true; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); for(int i=0;i<MX;i++) for(int j=i;j<MX;j++) dp[i][j]=2e18; cin>>N; cin>>s; cin>>A>>B>>C; s='#'+s; for(int l=N;l>0;l--) { for(int r=l;r<=N;r++) { dp[l][r]=min(dp[l][r],dp[l][r-1]+A); for(int k=0;k<=N;k++) ndp[k]=2e18; int len=r-l+1; ndp[r]=min(dp[l][r]+B+C,dp[l][r]+B+dp[l][r]); for(int k=r+1;k<=N;k++) { if(ok(l,r,k-len+1,k)) ndp[k]=min(ndp[k],ndp[k-len]+C); ndp[k]=min(ndp[k],ndp[k-1]+A); } for(int k=r+1;k<=N;k++) { dp[l][k]=min(dp[l][k],ndp[k]); } dp[l-1][r]=min(dp[l-1][r],dp[l][r]+A); } } cout<<dp[1][N]<<'\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...