제출 #715959

#제출 시각아이디문제언어결과실행 시간메모리
715959Darren0724Copy and Paste 3 (JOI22_copypaste3)C++17
25 / 100
3058 ms52812 KiB
#pragma GCC optimize("Ofast","O3","unroll-loops") #pragma GCC target("avx2") #include<bits/stdc++.h> using namespace std; #define int long long #define all(x) x.begin(),x.end() #define x first #define y second #define endl '\n' const int K=29,mod=1234567891; signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n;cin>>n; vector<char> v(n+1); for(int i=1;i<=n;i++){ cin>>v[i]; } int A,B,C;cin>>A>>B>>C; vector<vector<int>> h(n+2,vector<int>(n+2)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j++){ h[i][j]=h[i][j-1]*K+v[j]-'a'+1; h[i][j]%=mod; } } vector<vector<int>> dp(n+2,vector<int>(n+2)); for(int i=1;i<=n;i++){ for(int j=1;j+i-1<=n;j++){ int k=j+i-1; //cout<<j<<' '<<k<<endl; dp[j][k]=min(dp[j+1][k],dp[j][k-1])+A; for(int p=1;p<i;p++){ int cnt=0,cnt1=0; int j1=j; while(j1<=k){ if(j1+p-1<=k&&h[j][j+p-1]==h[j1][j1+p-1]){ cnt++; j1=j1+p; } else{ cnt1++; j1++; } } dp[j][k]=min(dp[j][k],dp[j][j+p-1]+A*cnt1+B+C*cnt); } } } cout<<dp[1][n]<<endl; 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...