This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <string>
using namespace std;
#define v vector
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
int main(){
int N;
cin>>N;
string S;
cin>>S;
ll A,B,C;
cin>>A>>B>>C;
map<string, int> subToInd;
map<pii, int> pairToInd;
v<set<int>> indToStarts(N*N+100);
int subInd=1;
for(int l=0; l<N; l++){
string sub="";
for(int r=l; r<N; r++){
sub.push_back(S[r]);
if(subToInd[sub]==0) subToInd[sub]=subInd++;
pairToInd[{l,r-l+1}] = subToInd[sub];
indToStarts[subToInd[sub]].insert(l);
}
}
v<v<int>> nextOccur(N,v<int>(N+1,N));
for(int i=N-1; i>=0; i--){
for(int s=1; s<=N-i; s++){
int ind=pairToInd[{i,s}];
auto next = indToStarts[ind].lower_bound(i+s);
if(next!=indToStarts[ind].end()) nextOccur[i][s]=(*next);
}
}
if(N==2500) return 0;
v<v<ll>> dp(N, v<ll>(N,1e17));
for(int s=1; s<=N; s++){
for(int l=N-1; l>=0; l--){
dp[l][l]=A;
if(s!=1 && l+s-1<N){
dp[l][l+s-1] = min(dp[l][l+s-1], A+dp[l+1][l+s-1]);
dp[l][l+s-1] = min(dp[l][l+s-1], dp[l][l+s-1-1]+A);
}
int num=2, nex=nextOccur[l][s];
while(nex<N){
int r=nex+s-1;
dp[l][r] = min(dp[l][r], dp[l][l+s-1]+B+C*num+(r-l+1 - num*s)*A);
dp[l][r] = min(dp[l][r], A+dp[l+1][r]);
dp[l][r] = min(dp[l][r], dp[l][r-1]+A);
nex=nextOccur[nex][s];
num++;
}
}
}
cout<<dp[0][N-1]<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |