#include <bits/stdc++.h>
#define f first
#define s second
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define vec vector
#define pb push_back
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))
#define fast_resp ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<int,ll> pil;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
const ll inf=1e18;
const int N=2500+3;
ll dp[N][N];
///l,r,prefix
//int pref[N][N];
vec<int> zet[N];
vec<int> z_func(string s){
int l=0,r=-1;
vec<int> zt(sz(s),0);
for(int i=1;i<sz(s);i++){
zt[i]=(i>r?0:min(r-i+1,zt[i-l]));
while(i+zt[i]<sz(s) && s[i+zt[i]]==s[zt[i]]) ++zt[i];
if(i+zt[i]-1>r){
r=i+zt[i]-1;
l=i;
}
}
return zt;
}
signed main(){
fast_resp;
int n;
string s;
cin>>n>>s;
int a,b,c;
cin>>a>>b>>c;
for(int j=0;j<N;j++){
for(int k=0;k<N;k++)
dp[j][k]=inf;
}
vec<vec<int>>nxt(n,vec<int>(n+1,-1));
for(int i=0;i<n;i++){
zet[i]=z_func(s.substr(i,n-i)+'#'+s.substr(i,n-i));
int last=0;
for(int j=i;j<n;j++){
// if((last+1)==1 && i==2){
// i=2;
// cout<<zet[i][j-i+n-i+1]<<endl;
// }
while(last+1<=zet[i][j-i+n-i+1] && (j-i)>=last+1){
++last;
// cout<<"WO "<<i<<' '<<last<<' '<<j<<endl;
nxt[i][last]=j;
}
}
}
for(int l=n-1;l>=0;l--){
for(int r=l;r<n;r++){
if(l==r) dp[l][r]=a+b;
// else{
if(l) umin(dp[l-1][r],dp[l][r]+a);
if(r+1<n) umin(dp[l][r+1],dp[l][r]+a);
ll total=dp[l][r]+c;
// if(l==2 && r==2){
// l=r=2;
// l=2;
// }
/// i'ma b
int j=nxt[l][r-l+1];
int last=r;
// cout<<"L "<<l<<' '<<r<<endl;
while(j!=-1){
// assert(j>last);
// cout<<"HEY "<<j-last-1<<endl;
total+=1ll*(j-last-1)*a;total+=c;
umin(dp[l][j+r-l],total+b);
last=j+r-l;
j=nxt[j][r-l+1];
}
// cout<<endl;
// }
}
}
// cout<<dp[2][8]<<endl;
cout<<dp[0][n-1]-b;
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49300 KB |
Output is correct |
3 |
Correct |
21 ms |
49360 KB |
Output is correct |
4 |
Correct |
21 ms |
49304 KB |
Output is correct |
5 |
Correct |
21 ms |
49352 KB |
Output is correct |
6 |
Correct |
23 ms |
49344 KB |
Output is correct |
7 |
Correct |
21 ms |
49364 KB |
Output is correct |
8 |
Correct |
20 ms |
49300 KB |
Output is correct |
9 |
Correct |
21 ms |
49364 KB |
Output is correct |
10 |
Correct |
21 ms |
49364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49364 KB |
Output is correct |
3 |
Correct |
195 ms |
75668 KB |
Output is correct |
4 |
Correct |
249 ms |
80116 KB |
Output is correct |
5 |
Correct |
345 ms |
85232 KB |
Output is correct |
6 |
Correct |
410 ms |
91316 KB |
Output is correct |
7 |
Correct |
490 ms |
98488 KB |
Output is correct |
8 |
Correct |
504 ms |
98548 KB |
Output is correct |
9 |
Correct |
497 ms |
98484 KB |
Output is correct |
10 |
Correct |
23 ms |
49308 KB |
Output is correct |
11 |
Correct |
22 ms |
49304 KB |
Output is correct |
12 |
Correct |
21 ms |
49316 KB |
Output is correct |
13 |
Correct |
20 ms |
49300 KB |
Output is correct |
14 |
Correct |
20 ms |
49364 KB |
Output is correct |
15 |
Correct |
22 ms |
49364 KB |
Output is correct |
16 |
Correct |
22 ms |
49364 KB |
Output is correct |
17 |
Correct |
21 ms |
49296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49300 KB |
Output is correct |
3 |
Correct |
21 ms |
49360 KB |
Output is correct |
4 |
Correct |
21 ms |
49304 KB |
Output is correct |
5 |
Correct |
21 ms |
49352 KB |
Output is correct |
6 |
Correct |
23 ms |
49344 KB |
Output is correct |
7 |
Correct |
21 ms |
49364 KB |
Output is correct |
8 |
Correct |
20 ms |
49300 KB |
Output is correct |
9 |
Correct |
21 ms |
49364 KB |
Output is correct |
10 |
Correct |
21 ms |
49364 KB |
Output is correct |
11 |
Correct |
21 ms |
49364 KB |
Output is correct |
12 |
Correct |
25 ms |
49364 KB |
Output is correct |
13 |
Correct |
19 ms |
49404 KB |
Output is correct |
14 |
Correct |
24 ms |
49364 KB |
Output is correct |
15 |
Correct |
21 ms |
49388 KB |
Output is correct |
16 |
Correct |
21 ms |
49392 KB |
Output is correct |
17 |
Correct |
23 ms |
49332 KB |
Output is correct |
18 |
Correct |
20 ms |
49388 KB |
Output is correct |
19 |
Correct |
26 ms |
49364 KB |
Output is correct |
20 |
Correct |
22 ms |
49412 KB |
Output is correct |
21 |
Correct |
21 ms |
49356 KB |
Output is correct |
22 |
Correct |
21 ms |
49364 KB |
Output is correct |
23 |
Correct |
22 ms |
49356 KB |
Output is correct |
24 |
Correct |
24 ms |
49316 KB |
Output is correct |
25 |
Correct |
21 ms |
49280 KB |
Output is correct |
26 |
Correct |
21 ms |
49364 KB |
Output is correct |
27 |
Correct |
23 ms |
49396 KB |
Output is correct |
28 |
Correct |
24 ms |
49332 KB |
Output is correct |
29 |
Correct |
21 ms |
49332 KB |
Output is correct |
30 |
Correct |
21 ms |
49364 KB |
Output is correct |
31 |
Correct |
22 ms |
49364 KB |
Output is correct |
32 |
Correct |
21 ms |
49400 KB |
Output is correct |
33 |
Correct |
21 ms |
49404 KB |
Output is correct |
34 |
Correct |
21 ms |
49424 KB |
Output is correct |
35 |
Correct |
21 ms |
49364 KB |
Output is correct |
36 |
Correct |
22 ms |
49300 KB |
Output is correct |
37 |
Correct |
22 ms |
49364 KB |
Output is correct |
38 |
Correct |
21 ms |
49352 KB |
Output is correct |
39 |
Correct |
21 ms |
49384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49300 KB |
Output is correct |
3 |
Correct |
21 ms |
49360 KB |
Output is correct |
4 |
Correct |
21 ms |
49304 KB |
Output is correct |
5 |
Correct |
21 ms |
49352 KB |
Output is correct |
6 |
Correct |
23 ms |
49344 KB |
Output is correct |
7 |
Correct |
21 ms |
49364 KB |
Output is correct |
8 |
Correct |
20 ms |
49300 KB |
Output is correct |
9 |
Correct |
21 ms |
49364 KB |
Output is correct |
10 |
Correct |
21 ms |
49364 KB |
Output is correct |
11 |
Correct |
21 ms |
49364 KB |
Output is correct |
12 |
Correct |
25 ms |
49364 KB |
Output is correct |
13 |
Correct |
19 ms |
49404 KB |
Output is correct |
14 |
Correct |
24 ms |
49364 KB |
Output is correct |
15 |
Correct |
21 ms |
49388 KB |
Output is correct |
16 |
Correct |
21 ms |
49392 KB |
Output is correct |
17 |
Correct |
23 ms |
49332 KB |
Output is correct |
18 |
Correct |
20 ms |
49388 KB |
Output is correct |
19 |
Correct |
26 ms |
49364 KB |
Output is correct |
20 |
Correct |
22 ms |
49412 KB |
Output is correct |
21 |
Correct |
21 ms |
49356 KB |
Output is correct |
22 |
Correct |
21 ms |
49364 KB |
Output is correct |
23 |
Correct |
22 ms |
49356 KB |
Output is correct |
24 |
Correct |
24 ms |
49316 KB |
Output is correct |
25 |
Correct |
21 ms |
49280 KB |
Output is correct |
26 |
Correct |
21 ms |
49364 KB |
Output is correct |
27 |
Correct |
23 ms |
49396 KB |
Output is correct |
28 |
Correct |
24 ms |
49332 KB |
Output is correct |
29 |
Correct |
21 ms |
49332 KB |
Output is correct |
30 |
Correct |
21 ms |
49364 KB |
Output is correct |
31 |
Correct |
22 ms |
49364 KB |
Output is correct |
32 |
Correct |
21 ms |
49400 KB |
Output is correct |
33 |
Correct |
21 ms |
49404 KB |
Output is correct |
34 |
Correct |
21 ms |
49424 KB |
Output is correct |
35 |
Correct |
21 ms |
49364 KB |
Output is correct |
36 |
Correct |
22 ms |
49300 KB |
Output is correct |
37 |
Correct |
22 ms |
49364 KB |
Output is correct |
38 |
Correct |
21 ms |
49352 KB |
Output is correct |
39 |
Correct |
21 ms |
49384 KB |
Output is correct |
40 |
Correct |
21 ms |
49364 KB |
Output is correct |
41 |
Correct |
22 ms |
49620 KB |
Output is correct |
42 |
Correct |
22 ms |
49716 KB |
Output is correct |
43 |
Correct |
22 ms |
49672 KB |
Output is correct |
44 |
Correct |
23 ms |
49696 KB |
Output is correct |
45 |
Correct |
23 ms |
49688 KB |
Output is correct |
46 |
Correct |
22 ms |
49724 KB |
Output is correct |
47 |
Correct |
20 ms |
49620 KB |
Output is correct |
48 |
Correct |
20 ms |
49840 KB |
Output is correct |
49 |
Correct |
22 ms |
49736 KB |
Output is correct |
50 |
Correct |
21 ms |
49684 KB |
Output is correct |
51 |
Correct |
22 ms |
49644 KB |
Output is correct |
52 |
Correct |
22 ms |
49652 KB |
Output is correct |
53 |
Correct |
22 ms |
49692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49300 KB |
Output is correct |
3 |
Correct |
21 ms |
49360 KB |
Output is correct |
4 |
Correct |
21 ms |
49304 KB |
Output is correct |
5 |
Correct |
21 ms |
49352 KB |
Output is correct |
6 |
Correct |
23 ms |
49344 KB |
Output is correct |
7 |
Correct |
21 ms |
49364 KB |
Output is correct |
8 |
Correct |
20 ms |
49300 KB |
Output is correct |
9 |
Correct |
21 ms |
49364 KB |
Output is correct |
10 |
Correct |
21 ms |
49364 KB |
Output is correct |
11 |
Correct |
21 ms |
49364 KB |
Output is correct |
12 |
Correct |
25 ms |
49364 KB |
Output is correct |
13 |
Correct |
19 ms |
49404 KB |
Output is correct |
14 |
Correct |
24 ms |
49364 KB |
Output is correct |
15 |
Correct |
21 ms |
49388 KB |
Output is correct |
16 |
Correct |
21 ms |
49392 KB |
Output is correct |
17 |
Correct |
23 ms |
49332 KB |
Output is correct |
18 |
Correct |
20 ms |
49388 KB |
Output is correct |
19 |
Correct |
26 ms |
49364 KB |
Output is correct |
20 |
Correct |
22 ms |
49412 KB |
Output is correct |
21 |
Correct |
21 ms |
49356 KB |
Output is correct |
22 |
Correct |
21 ms |
49364 KB |
Output is correct |
23 |
Correct |
22 ms |
49356 KB |
Output is correct |
24 |
Correct |
24 ms |
49316 KB |
Output is correct |
25 |
Correct |
21 ms |
49280 KB |
Output is correct |
26 |
Correct |
21 ms |
49364 KB |
Output is correct |
27 |
Correct |
23 ms |
49396 KB |
Output is correct |
28 |
Correct |
24 ms |
49332 KB |
Output is correct |
29 |
Correct |
21 ms |
49332 KB |
Output is correct |
30 |
Correct |
21 ms |
49364 KB |
Output is correct |
31 |
Correct |
22 ms |
49364 KB |
Output is correct |
32 |
Correct |
21 ms |
49400 KB |
Output is correct |
33 |
Correct |
21 ms |
49404 KB |
Output is correct |
34 |
Correct |
21 ms |
49424 KB |
Output is correct |
35 |
Correct |
21 ms |
49364 KB |
Output is correct |
36 |
Correct |
22 ms |
49300 KB |
Output is correct |
37 |
Correct |
22 ms |
49364 KB |
Output is correct |
38 |
Correct |
21 ms |
49352 KB |
Output is correct |
39 |
Correct |
21 ms |
49384 KB |
Output is correct |
40 |
Correct |
21 ms |
49364 KB |
Output is correct |
41 |
Correct |
22 ms |
49620 KB |
Output is correct |
42 |
Correct |
22 ms |
49716 KB |
Output is correct |
43 |
Correct |
22 ms |
49672 KB |
Output is correct |
44 |
Correct |
23 ms |
49696 KB |
Output is correct |
45 |
Correct |
23 ms |
49688 KB |
Output is correct |
46 |
Correct |
22 ms |
49724 KB |
Output is correct |
47 |
Correct |
20 ms |
49620 KB |
Output is correct |
48 |
Correct |
20 ms |
49840 KB |
Output is correct |
49 |
Correct |
22 ms |
49736 KB |
Output is correct |
50 |
Correct |
21 ms |
49684 KB |
Output is correct |
51 |
Correct |
22 ms |
49644 KB |
Output is correct |
52 |
Correct |
22 ms |
49652 KB |
Output is correct |
53 |
Correct |
22 ms |
49692 KB |
Output is correct |
54 |
Correct |
25 ms |
50948 KB |
Output is correct |
55 |
Correct |
56 ms |
57280 KB |
Output is correct |
56 |
Correct |
41 ms |
57316 KB |
Output is correct |
57 |
Correct |
36 ms |
57196 KB |
Output is correct |
58 |
Correct |
36 ms |
57236 KB |
Output is correct |
59 |
Correct |
36 ms |
57372 KB |
Output is correct |
60 |
Correct |
32 ms |
57268 KB |
Output is correct |
61 |
Correct |
35 ms |
57188 KB |
Output is correct |
62 |
Correct |
61 ms |
57160 KB |
Output is correct |
63 |
Correct |
32 ms |
57300 KB |
Output is correct |
64 |
Correct |
32 ms |
57232 KB |
Output is correct |
65 |
Correct |
39 ms |
57300 KB |
Output is correct |
66 |
Correct |
39 ms |
57256 KB |
Output is correct |
67 |
Correct |
33 ms |
57264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
49364 KB |
Output is correct |
2 |
Correct |
21 ms |
49300 KB |
Output is correct |
3 |
Correct |
21 ms |
49360 KB |
Output is correct |
4 |
Correct |
21 ms |
49304 KB |
Output is correct |
5 |
Correct |
21 ms |
49352 KB |
Output is correct |
6 |
Correct |
23 ms |
49344 KB |
Output is correct |
7 |
Correct |
21 ms |
49364 KB |
Output is correct |
8 |
Correct |
20 ms |
49300 KB |
Output is correct |
9 |
Correct |
21 ms |
49364 KB |
Output is correct |
10 |
Correct |
21 ms |
49364 KB |
Output is correct |
11 |
Correct |
21 ms |
49364 KB |
Output is correct |
12 |
Correct |
21 ms |
49364 KB |
Output is correct |
13 |
Correct |
195 ms |
75668 KB |
Output is correct |
14 |
Correct |
249 ms |
80116 KB |
Output is correct |
15 |
Correct |
345 ms |
85232 KB |
Output is correct |
16 |
Correct |
410 ms |
91316 KB |
Output is correct |
17 |
Correct |
490 ms |
98488 KB |
Output is correct |
18 |
Correct |
504 ms |
98548 KB |
Output is correct |
19 |
Correct |
497 ms |
98484 KB |
Output is correct |
20 |
Correct |
23 ms |
49308 KB |
Output is correct |
21 |
Correct |
22 ms |
49304 KB |
Output is correct |
22 |
Correct |
21 ms |
49316 KB |
Output is correct |
23 |
Correct |
20 ms |
49300 KB |
Output is correct |
24 |
Correct |
20 ms |
49364 KB |
Output is correct |
25 |
Correct |
22 ms |
49364 KB |
Output is correct |
26 |
Correct |
22 ms |
49364 KB |
Output is correct |
27 |
Correct |
21 ms |
49296 KB |
Output is correct |
28 |
Correct |
21 ms |
49364 KB |
Output is correct |
29 |
Correct |
25 ms |
49364 KB |
Output is correct |
30 |
Correct |
19 ms |
49404 KB |
Output is correct |
31 |
Correct |
24 ms |
49364 KB |
Output is correct |
32 |
Correct |
21 ms |
49388 KB |
Output is correct |
33 |
Correct |
21 ms |
49392 KB |
Output is correct |
34 |
Correct |
23 ms |
49332 KB |
Output is correct |
35 |
Correct |
20 ms |
49388 KB |
Output is correct |
36 |
Correct |
26 ms |
49364 KB |
Output is correct |
37 |
Correct |
22 ms |
49412 KB |
Output is correct |
38 |
Correct |
21 ms |
49356 KB |
Output is correct |
39 |
Correct |
21 ms |
49364 KB |
Output is correct |
40 |
Correct |
22 ms |
49356 KB |
Output is correct |
41 |
Correct |
24 ms |
49316 KB |
Output is correct |
42 |
Correct |
21 ms |
49280 KB |
Output is correct |
43 |
Correct |
21 ms |
49364 KB |
Output is correct |
44 |
Correct |
23 ms |
49396 KB |
Output is correct |
45 |
Correct |
24 ms |
49332 KB |
Output is correct |
46 |
Correct |
21 ms |
49332 KB |
Output is correct |
47 |
Correct |
21 ms |
49364 KB |
Output is correct |
48 |
Correct |
22 ms |
49364 KB |
Output is correct |
49 |
Correct |
21 ms |
49400 KB |
Output is correct |
50 |
Correct |
21 ms |
49404 KB |
Output is correct |
51 |
Correct |
21 ms |
49424 KB |
Output is correct |
52 |
Correct |
21 ms |
49364 KB |
Output is correct |
53 |
Correct |
22 ms |
49300 KB |
Output is correct |
54 |
Correct |
22 ms |
49364 KB |
Output is correct |
55 |
Correct |
21 ms |
49352 KB |
Output is correct |
56 |
Correct |
21 ms |
49384 KB |
Output is correct |
57 |
Correct |
21 ms |
49364 KB |
Output is correct |
58 |
Correct |
22 ms |
49620 KB |
Output is correct |
59 |
Correct |
22 ms |
49716 KB |
Output is correct |
60 |
Correct |
22 ms |
49672 KB |
Output is correct |
61 |
Correct |
23 ms |
49696 KB |
Output is correct |
62 |
Correct |
23 ms |
49688 KB |
Output is correct |
63 |
Correct |
22 ms |
49724 KB |
Output is correct |
64 |
Correct |
20 ms |
49620 KB |
Output is correct |
65 |
Correct |
20 ms |
49840 KB |
Output is correct |
66 |
Correct |
22 ms |
49736 KB |
Output is correct |
67 |
Correct |
21 ms |
49684 KB |
Output is correct |
68 |
Correct |
22 ms |
49644 KB |
Output is correct |
69 |
Correct |
22 ms |
49652 KB |
Output is correct |
70 |
Correct |
22 ms |
49692 KB |
Output is correct |
71 |
Correct |
25 ms |
50948 KB |
Output is correct |
72 |
Correct |
56 ms |
57280 KB |
Output is correct |
73 |
Correct |
41 ms |
57316 KB |
Output is correct |
74 |
Correct |
36 ms |
57196 KB |
Output is correct |
75 |
Correct |
36 ms |
57236 KB |
Output is correct |
76 |
Correct |
36 ms |
57372 KB |
Output is correct |
77 |
Correct |
32 ms |
57268 KB |
Output is correct |
78 |
Correct |
35 ms |
57188 KB |
Output is correct |
79 |
Correct |
61 ms |
57160 KB |
Output is correct |
80 |
Correct |
32 ms |
57300 KB |
Output is correct |
81 |
Correct |
32 ms |
57232 KB |
Output is correct |
82 |
Correct |
39 ms |
57300 KB |
Output is correct |
83 |
Correct |
39 ms |
57256 KB |
Output is correct |
84 |
Correct |
33 ms |
57264 KB |
Output is correct |
85 |
Correct |
75 ms |
69056 KB |
Output is correct |
86 |
Correct |
157 ms |
98428 KB |
Output is correct |
87 |
Correct |
131 ms |
98484 KB |
Output is correct |
88 |
Correct |
97 ms |
98376 KB |
Output is correct |
89 |
Correct |
90 ms |
98472 KB |
Output is correct |
90 |
Correct |
84 ms |
98480 KB |
Output is correct |
91 |
Correct |
126 ms |
98392 KB |
Output is correct |
92 |
Correct |
176 ms |
98384 KB |
Output is correct |
93 |
Correct |
92 ms |
98432 KB |
Output is correct |
94 |
Correct |
95 ms |
98380 KB |
Output is correct |
95 |
Correct |
160 ms |
98440 KB |
Output is correct |
96 |
Correct |
162 ms |
98484 KB |
Output is correct |
97 |
Correct |
85 ms |
98420 KB |
Output is correct |