/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2510;
const ll base = 29, inf = 1e18;
int n;
ll a, b, c, h[maxn], pw[maxn];
string s;
unordered_map < ll, vector < int > > occ;
unordered_map < ll, ll > hs_dp, pt;
unordered_map < ll, int > nxt[maxn];
ll range_hash[maxn][maxn];
ll get_hash(int i, int j)
{
return range_hash[i][j];
}
void solve()
{
cin >> n >> s >> a >> b >> c;
s = "#" + s;
pw[0] = 1;
for (int i = 1; i <= n; i ++)
{
h[i] = h[i - 1] * base + (s[i] - 'a' + 1);
pw[i] = pw[i - 1] * base;
}
for (int i = 1; i <= n; i ++)
for (int j = i; j <= n; j ++)
range_hash[i][j] = h[j] - h[i - 1] * pw[j - i + 1];
for (int i = n; i > 0; i --)
{
for (int p = i; p <= n; p ++)
{
ll cur_hs = get_hash(i, p);
occ[cur_hs].push_back(i);
/**cout << "hash " << i << " " << p << endl;
cout << "occurrences: ";
for (int ds : occ[cur_hs])
cout << ds << " ";
cout << endl;*/
if (occ[cur_hs].size() == 1)
{
hs_dp[cur_hs] = hs_dp[get_hash(i + 1, p)] + a;
nxt[p][cur_hs] = n + 1;
pt[cur_hs] = -1;
}
else
{
hs_dp[cur_hs] = min(hs_dp[cur_hs], hs_dp[get_hash(i + 1, p)] + a);
if (pt[cur_hs] == -1)
{
pt[cur_hs] ++;
}
while(occ[cur_hs][pt[cur_hs]] > p)
pt[cur_hs] ++;
pt[cur_hs] --;
if (pt[cur_hs] == -1)
nxt[p][cur_hs] = n + 1;
else
nxt[p][cur_hs] = occ[cur_hs][pt[cur_hs]] + (p - i);
///cout << "step " << i << " " << p << " " << nxt[p][cur_hs] << endl;
}
}
for (int k = i; k <= n; k ++)
{
ll clip_hash, clip_len = k - i + 1;
clip_hash = h[k] - h[i - 1] * pw[clip_len];
ll cost = hs_dp[clip_hash] + b + c;
if (occ[get_hash(i, k)].size() < 2)
break;
int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
///dp[get_hash(i, k)] = min(dp[get_hash(i, k)], cos);
///cout << "-------------------" << endl;
///cout << i << " " << k << endl;
while(pos <= n)
{
///cout << pos << " " << cost << endl;
int to = nxt[pos][clip_hash];
if (to > n)
break;
cost = cost + (to - pos - clip_len) * a;
cost = cost + c;
///cout << "stop " << occ[clip_hash][pt] << endl;
///cost = cost + (occ[clip_hash][pt] - pos) * a;
///cost = cost + c;
pos = to;
hs_dp[get_hash(i, pos)] = min(hs_dp[get_hash(i, pos)], cost);
/**int to = pos + clip_len - 1;
if (to > n)
{
break;
}
if (get_hash(pos, to) == clip_hash)
{
cost = cost + c;
pos = pos + clip_len;
hs_dp[get_hash(i, to)] = min(hs_dp[get_hash(i, to)], cost);
}
else
{
pos ++;
cost += a;
}*/
}
}
for (int k = i; k <= n; k ++)
{
hs_dp[get_hash(i, k)] = min(hs_dp[get_hash(i, k)], hs_dp[get_hash(i, k - 1)] + a);
}
}
/**for (int i = 1; i <= n; i ++, cout << endl)
for (int j = i; j <= n; j ++)
cout << hs_dp[get_hash(i, j)] << " ";*/
cout << hs_dp[h[n]] << endl;
}
int main()
{
solve();
return 0;
}
Compilation message
copypaste3.cpp: In function 'void solve()':
copypaste3.cpp:99:26: warning: unused variable 'pt' [-Wunused-variable]
99 | int pos = k, pt = (int)(occ[clip_hash].size()) - 1;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
456 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Execution timed out |
3061 ms |
89752 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
456 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
452 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
452 KB |
Output is correct |
17 |
Correct |
1 ms |
448 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
572 KB |
Output is correct |
24 |
Correct |
1 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
1 ms |
584 KB |
Output is correct |
27 |
Correct |
1 ms |
576 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
1 ms |
584 KB |
Output is correct |
32 |
Correct |
1 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
596 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
452 KB |
Output is correct |
36 |
Correct |
1 ms |
448 KB |
Output is correct |
37 |
Correct |
1 ms |
456 KB |
Output is correct |
38 |
Correct |
1 ms |
468 KB |
Output is correct |
39 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
456 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
452 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
452 KB |
Output is correct |
17 |
Correct |
1 ms |
448 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
572 KB |
Output is correct |
24 |
Correct |
1 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
1 ms |
584 KB |
Output is correct |
27 |
Correct |
1 ms |
576 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
1 ms |
584 KB |
Output is correct |
32 |
Correct |
1 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
596 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
452 KB |
Output is correct |
36 |
Correct |
1 ms |
448 KB |
Output is correct |
37 |
Correct |
1 ms |
456 KB |
Output is correct |
38 |
Correct |
1 ms |
468 KB |
Output is correct |
39 |
Correct |
1 ms |
596 KB |
Output is correct |
40 |
Correct |
3 ms |
1492 KB |
Output is correct |
41 |
Correct |
16 ms |
2368 KB |
Output is correct |
42 |
Correct |
13 ms |
5436 KB |
Output is correct |
43 |
Correct |
12 ms |
5460 KB |
Output is correct |
44 |
Correct |
12 ms |
5460 KB |
Output is correct |
45 |
Correct |
12 ms |
5588 KB |
Output is correct |
46 |
Correct |
11 ms |
5556 KB |
Output is correct |
47 |
Correct |
16 ms |
3024 KB |
Output is correct |
48 |
Correct |
14 ms |
4416 KB |
Output is correct |
49 |
Correct |
12 ms |
4820 KB |
Output is correct |
50 |
Correct |
12 ms |
4820 KB |
Output is correct |
51 |
Correct |
15 ms |
4408 KB |
Output is correct |
52 |
Correct |
15 ms |
4448 KB |
Output is correct |
53 |
Correct |
11 ms |
5572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
456 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
468 KB |
Output is correct |
14 |
Correct |
1 ms |
452 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
452 KB |
Output is correct |
17 |
Correct |
1 ms |
448 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
1 ms |
580 KB |
Output is correct |
22 |
Correct |
1 ms |
596 KB |
Output is correct |
23 |
Correct |
1 ms |
572 KB |
Output is correct |
24 |
Correct |
1 ms |
596 KB |
Output is correct |
25 |
Correct |
1 ms |
596 KB |
Output is correct |
26 |
Correct |
1 ms |
584 KB |
Output is correct |
27 |
Correct |
1 ms |
576 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
596 KB |
Output is correct |
31 |
Correct |
1 ms |
584 KB |
Output is correct |
32 |
Correct |
1 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
596 KB |
Output is correct |
34 |
Correct |
1 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
452 KB |
Output is correct |
36 |
Correct |
1 ms |
448 KB |
Output is correct |
37 |
Correct |
1 ms |
456 KB |
Output is correct |
38 |
Correct |
1 ms |
468 KB |
Output is correct |
39 |
Correct |
1 ms |
596 KB |
Output is correct |
40 |
Correct |
3 ms |
1492 KB |
Output is correct |
41 |
Correct |
16 ms |
2368 KB |
Output is correct |
42 |
Correct |
13 ms |
5436 KB |
Output is correct |
43 |
Correct |
12 ms |
5460 KB |
Output is correct |
44 |
Correct |
12 ms |
5460 KB |
Output is correct |
45 |
Correct |
12 ms |
5588 KB |
Output is correct |
46 |
Correct |
11 ms |
5556 KB |
Output is correct |
47 |
Correct |
16 ms |
3024 KB |
Output is correct |
48 |
Correct |
14 ms |
4416 KB |
Output is correct |
49 |
Correct |
12 ms |
4820 KB |
Output is correct |
50 |
Correct |
12 ms |
4820 KB |
Output is correct |
51 |
Correct |
15 ms |
4408 KB |
Output is correct |
52 |
Correct |
15 ms |
4448 KB |
Output is correct |
53 |
Correct |
11 ms |
5572 KB |
Output is correct |
54 |
Correct |
135 ms |
25004 KB |
Output is correct |
55 |
Correct |
699 ms |
32388 KB |
Output is correct |
56 |
Correct |
1070 ms |
115612 KB |
Output is correct |
57 |
Correct |
1071 ms |
116076 KB |
Output is correct |
58 |
Correct |
1034 ms |
116368 KB |
Output is correct |
59 |
Correct |
1035 ms |
116600 KB |
Output is correct |
60 |
Correct |
1061 ms |
116748 KB |
Output is correct |
61 |
Correct |
771 ms |
67744 KB |
Output is correct |
62 |
Correct |
802 ms |
33048 KB |
Output is correct |
63 |
Correct |
1059 ms |
98944 KB |
Output is correct |
64 |
Correct |
1063 ms |
99648 KB |
Output is correct |
65 |
Correct |
959 ms |
72656 KB |
Output is correct |
66 |
Correct |
964 ms |
72616 KB |
Output is correct |
67 |
Correct |
1008 ms |
116640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
456 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
456 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Execution timed out |
3061 ms |
89752 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |