#include <bits/stdc++.h>
using namespace std;
char arr[2505];
long long A,B,C;
long long mem[2505*1305];
int ct = 1;
struct node{
int nid;
short len;
vector<short> vals;
node*ch[26];
vector<vector<short> >decomp;
node(int _len){
nid = ct++;
len = _len;
for (int x = 0; x<26; x++){
ch[x] = 0;
}
}
void construct(){
//printf("call construct len %lld\n",len);
int lgx = 1;
while ((1<<(lgx))<=vals.size()) lgx++;
decomp.resize(lgx);
for (int x = 0; x<vals.size(); x++){
decomp[0].push_back(lower_bound(vals.begin(),vals.end(),vals[x]+len)-vals.begin());
}
decomp[0].push_back(vals.size());
for (int x = 1; x<decomp.size(); x++){
for (int y = 0; y<=vals.size(); y++){
decomp[x].push_back(decomp[x-1][decomp[x-1][y]]);
}
}
}
void constructall(){
construct();
for (int x = 0; x<26; x++){
if (ch[x]!=0){
ch[x]->constructall();
}
}
}
int cntocc(int st, int en){
//printf("call cntocc %lld %lld, len %lld\n",st,en,len);
int cur = lower_bound(vals.begin(),vals.end(),st)-vals.begin();
int ans = 1;
int r = upper_bound(vals.begin(),vals.end(),en-len)-vals.begin();
for (int x = (int)decomp.size()-1; x>=0; x--){
if (decomp[x][cur]<r){
ans += (1<<x);
cur = decomp[x][cur];
}
}
return ans;
}
}*rt;
node* pt[2505][2505];
inline int cntocc(int a, int b, int st, int en){
return pt[a][b]->cntocc(st,en);
}
/*
long long func(int a, int b){
if (a==b) return 0;
if (mem[pt[a][b]->nid]!=-1) return mem[pt[a][b]->nid];
long long ans = func(a+1,b)+A;
for (int x = 1; x<b-a; x++){
long long t = func(a,a+x);
int t2 = cntocc(a,a+x,a,b);
ans = min(ans,t+B+t2*C+(b-a-x*t2)*A);
if (t2==1) break;
}
//printf("func %lld %lld = %lld\n",a,b,ans);
return mem[pt[a][b]->nid] = ans;
}
*/
main(){
int n;
scanf("%d",&n);
for (int x = 0; x<n; x++){
scanf(" %c",&arr[x]);
}
scanf("%lld%lld%lld",&A,&B,&C);
memset(mem,-1,sizeof(mem));
for (int x = 0; x<n; x++){
if (rt==0){
rt = new node(0);
}
node *cur = rt;
pt[x][x] = rt;
for (int y = x+1; y<=n; y++){
if (cur->ch[arr[y-1]-'a']==0){
cur->ch[arr[y-1]-'a'] = new node(y-x);
}
cur = cur->ch[arr[y-1]-'a'];
cur->vals.push_back(x);
pt[x][y] = cur;
}
}
pt[n][n] = rt;
rt->constructall();
mem[rt->nid] = 0;
for (int x = 1; x<=n; x++){
for (int y = 0; x+y<=n; y++){
int a = y;
int b = x+y;
//printf("a b %d %d\n",a,b);
if (mem[pt[a+1][b]->nid]!=-1) continue;
long long ans = mem[pt[a+1][b]->nid]+A;
for (int x = 1; x<b-a; x++){
long long t = mem[pt[a][a+x]->nid];
int t2 = cntocc(a,a+x,a,b);
ans = min(ans,t+B+t2*C+(b-a-x*t2)*A);
if (t2==1) break;
}
//printf("func %lld %lld = %lld\n",a,b,ans);
mem[pt[a][b]->nid] = ans;
}
}
printf("%lld",mem[pt[0][n]->nid]);
}
Compilation message
copypaste3.cpp: In member function 'void node::construct()':
copypaste3.cpp:25:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | while ((1<<(lgx))<=vals.size()) lgx++;
| ~~~~~~~~~~^~~~~~~~~~~~~
copypaste3.cpp:27:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for (int x = 0; x<vals.size(); x++){
| ~^~~~~~~~~~~~
copypaste3.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for (int x = 1; x<decomp.size(); x++){
| ~^~~~~~~~~~~~~~
copypaste3.cpp:32:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for (int y = 0; y<=vals.size(); y++){
| ~^~~~~~~~~~~~~
copypaste3.cpp: At global scope:
copypaste3.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main(){
| ^~~~
copypaste3.cpp: In function 'int main()':
copypaste3.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
copypaste3.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
86 | scanf(" %c",&arr[x]);
| ~~~~~^~~~~~~~~~~~~~~
copypaste3.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%lld%lld%lld",&A,&B,&C);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
25940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
25892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
