#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;
const ll maxn=2505;
const long long p=101, Mod=100000000069;
vector <ll> pos[maxn*maxn];
ll crr, go[maxn*maxn][26];
long long check[maxn*maxn];
ll pi[maxn][maxn], idx[maxn][maxn], cnt[maxn][maxn], R[maxn][maxn];
inline ll calc(ll l, ll r, ll q)
{
ll id=idx[l][r], len=r-l+1;
while (1)
{
ll p=upper_bound(pos[id].begin(), pos[id].end(), R[l][r])-pos[id].begin();
if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
cnt[l][r]++, R[l][r]=pos[id][p]+len-1;
}
return cnt[l][r];
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n;
string s; cin >> s; s='$'+s;
long long A, B, C; cin >> A >> B >> C;
vector <long long> num;
for (ll i=1; i<=n; i++)
{
for (ll j=i+1; j<=n; j++)
{
ll k=pi[i][j-1];
while (k && s[i+k]!=s[j])
k=pi[i][k-1];
pi[i][j]=k+(s[i+k]==s[j]);
}
ll p=0;
for (ll j=i; j<=n; j++)
{
ll c=s[j]-'a';
if (!go[p][c]) go[p][c]=++crr;
p=go[p][c], idx[i][j]=p;
pos[idx[i][j]].pb(i);
}
}
for (ll len=1; len<=n; len++)
{
for (ll i=1; i+len<=n+1; i++)
{
ll j=i+len-1, crr=pi[i][j];
if (check[idx[i][j]])
continue;
check[idx[i][j]]=A*len;
if (i<j) check[idx[i][j]]=min({check[idx[i][j]], check[idx[i+1][j]]+A, check[idx[i][j-1]]+A});
for (; crr; crr=pi[i][i+crr-1])
if (crr*2<=len)
{
ll c=calc(i, i+crr-1, j);
long long val=check[idx[i][i+crr-1]];
check[idx[i][j]]=min(check[idx[i][j]], val+B+C*c+A*(len-crr*c));
}
}
}
cout << check[idx[1][n]];
}
Compilation message
copypaste3.cpp: In function 'int calc(int, int, int)':
copypaste3.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if (p>=pos[id].size() || pos[id][p]+len-1>q) break;
| ~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
151632 KB |
Output is correct |
2 |
Correct |
48 ms |
151636 KB |
Output is correct |
3 |
Correct |
46 ms |
151644 KB |
Output is correct |
4 |
Correct |
49 ms |
151644 KB |
Output is correct |
5 |
Correct |
47 ms |
151632 KB |
Output is correct |
6 |
Correct |
48 ms |
151904 KB |
Output is correct |
7 |
Correct |
47 ms |
151636 KB |
Output is correct |
8 |
Correct |
47 ms |
151636 KB |
Output is correct |
9 |
Correct |
48 ms |
151752 KB |
Output is correct |
10 |
Correct |
47 ms |
151636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
151892 KB |
Output is correct |
2 |
Correct |
48 ms |
151748 KB |
Output is correct |
3 |
Correct |
116 ms |
194060 KB |
Output is correct |
4 |
Correct |
121 ms |
198700 KB |
Output is correct |
5 |
Correct |
138 ms |
203860 KB |
Output is correct |
6 |
Correct |
153 ms |
208928 KB |
Output is correct |
7 |
Correct |
190 ms |
213844 KB |
Output is correct |
8 |
Correct |
181 ms |
213856 KB |
Output is correct |
9 |
Correct |
169 ms |
213744 KB |
Output is correct |
10 |
Correct |
47 ms |
151640 KB |
Output is correct |
11 |
Correct |
48 ms |
151636 KB |
Output is correct |
12 |
Correct |
48 ms |
151740 KB |
Output is correct |
13 |
Correct |
46 ms |
151644 KB |
Output is correct |
14 |
Correct |
47 ms |
151644 KB |
Output is correct |
15 |
Correct |
46 ms |
151632 KB |
Output is correct |
16 |
Correct |
48 ms |
151648 KB |
Output is correct |
17 |
Correct |
49 ms |
151716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
151632 KB |
Output is correct |
2 |
Correct |
48 ms |
151636 KB |
Output is correct |
3 |
Correct |
46 ms |
151644 KB |
Output is correct |
4 |
Correct |
49 ms |
151644 KB |
Output is correct |
5 |
Correct |
47 ms |
151632 KB |
Output is correct |
6 |
Correct |
48 ms |
151904 KB |
Output is correct |
7 |
Correct |
47 ms |
151636 KB |
Output is correct |
8 |
Correct |
47 ms |
151636 KB |
Output is correct |
9 |
Correct |
48 ms |
151752 KB |
Output is correct |
10 |
Correct |
47 ms |
151636 KB |
Output is correct |
11 |
Correct |
47 ms |
151640 KB |
Output is correct |
12 |
Correct |
50 ms |
151804 KB |
Output is correct |
13 |
Incorrect |
50 ms |
151896 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
151632 KB |
Output is correct |
2 |
Correct |
48 ms |
151636 KB |
Output is correct |
3 |
Correct |
46 ms |
151644 KB |
Output is correct |
4 |
Correct |
49 ms |
151644 KB |
Output is correct |
5 |
Correct |
47 ms |
151632 KB |
Output is correct |
6 |
Correct |
48 ms |
151904 KB |
Output is correct |
7 |
Correct |
47 ms |
151636 KB |
Output is correct |
8 |
Correct |
47 ms |
151636 KB |
Output is correct |
9 |
Correct |
48 ms |
151752 KB |
Output is correct |
10 |
Correct |
47 ms |
151636 KB |
Output is correct |
11 |
Correct |
47 ms |
151640 KB |
Output is correct |
12 |
Correct |
50 ms |
151804 KB |
Output is correct |
13 |
Incorrect |
50 ms |
151896 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
151632 KB |
Output is correct |
2 |
Correct |
48 ms |
151636 KB |
Output is correct |
3 |
Correct |
46 ms |
151644 KB |
Output is correct |
4 |
Correct |
49 ms |
151644 KB |
Output is correct |
5 |
Correct |
47 ms |
151632 KB |
Output is correct |
6 |
Correct |
48 ms |
151904 KB |
Output is correct |
7 |
Correct |
47 ms |
151636 KB |
Output is correct |
8 |
Correct |
47 ms |
151636 KB |
Output is correct |
9 |
Correct |
48 ms |
151752 KB |
Output is correct |
10 |
Correct |
47 ms |
151636 KB |
Output is correct |
11 |
Correct |
47 ms |
151640 KB |
Output is correct |
12 |
Correct |
50 ms |
151804 KB |
Output is correct |
13 |
Incorrect |
50 ms |
151896 KB |
Output isn't correct |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
151632 KB |
Output is correct |
2 |
Correct |
48 ms |
151636 KB |
Output is correct |
3 |
Correct |
46 ms |
151644 KB |
Output is correct |
4 |
Correct |
49 ms |
151644 KB |
Output is correct |
5 |
Correct |
47 ms |
151632 KB |
Output is correct |
6 |
Correct |
48 ms |
151904 KB |
Output is correct |
7 |
Correct |
47 ms |
151636 KB |
Output is correct |
8 |
Correct |
47 ms |
151636 KB |
Output is correct |
9 |
Correct |
48 ms |
151752 KB |
Output is correct |
10 |
Correct |
47 ms |
151636 KB |
Output is correct |
11 |
Correct |
47 ms |
151892 KB |
Output is correct |
12 |
Correct |
48 ms |
151748 KB |
Output is correct |
13 |
Correct |
116 ms |
194060 KB |
Output is correct |
14 |
Correct |
121 ms |
198700 KB |
Output is correct |
15 |
Correct |
138 ms |
203860 KB |
Output is correct |
16 |
Correct |
153 ms |
208928 KB |
Output is correct |
17 |
Correct |
190 ms |
213844 KB |
Output is correct |
18 |
Correct |
181 ms |
213856 KB |
Output is correct |
19 |
Correct |
169 ms |
213744 KB |
Output is correct |
20 |
Correct |
47 ms |
151640 KB |
Output is correct |
21 |
Correct |
48 ms |
151636 KB |
Output is correct |
22 |
Correct |
48 ms |
151740 KB |
Output is correct |
23 |
Correct |
46 ms |
151644 KB |
Output is correct |
24 |
Correct |
47 ms |
151644 KB |
Output is correct |
25 |
Correct |
46 ms |
151632 KB |
Output is correct |
26 |
Correct |
48 ms |
151648 KB |
Output is correct |
27 |
Correct |
49 ms |
151716 KB |
Output is correct |
28 |
Correct |
47 ms |
151640 KB |
Output is correct |
29 |
Correct |
50 ms |
151804 KB |
Output is correct |
30 |
Incorrect |
50 ms |
151896 KB |
Output isn't correct |
31 |
Halted |
0 ms |
0 KB |
- |