#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)
pair<int, int> mod={(int)1e9+7, (int)1e9+9};
const int base=311;
struct Hash{
pair<int, int> value;
Hash (int x=0){
value={x%mod.first, x%mod.second};
}
Hash (int x, int y){
value={x, y};
}
Hash operator-(){
return Hash((mod.first-value.first)%mod.first,
(mod.second-value.second)%mod.second);
}
Hash operator+(Hash b){
return Hash((value.first+b.value.first)%mod.first,
(value.second+b.value.second)%mod.second);
}
Hash operator*(Hash b){
return Hash(value.first*b.value.first%mod.first,
value.second*b.value.second%mod.second);
}
bool operator<(Hash b) const {
return value<b.value;
}
bool operator==(Hash b) const {
return value==b.value;
}
};
const int N=2510, LG=12;
int f[N][N], add, cut, paste, n;
vector<pair<int, int>> g[N][N];
Hash pf[N];
Hash pw[N];
string s;
Hash get(int l, int r){
return pf[r]+(-pf[l-1])*pw[r-l+1];
}
void precalc(){
pw[0]=1;
for (int i=1; i<=n; ++i){
pw[i]=pw[i-1]*base;
}
for (int i=1; i<=n; ++i){
pf[i]=pf[i-1]*base+s[i];
}
for (int len=1; len<=n; ++len){
map<pair<int, int>, vector<int>> mp;
for (int r=len; r<=n; ++r){
int l=r-len+1;
mp[get(l, r).value].push_back(l);
}
vector<int> jump(n+1, -1);
for (auto &tmp:mp){
vector<int> &v=tmp.second;
for (int i=0, j=0; i<isz(v); ++i){
while (j<isz(v) && v[j]-v[i]<len) ++j;
jump[v[i]]=j==isz(v)?-1:v[j];
}
}
for (int i=1; i<=n; ++i){
int j=jump[i], cnt=2;
while (j!=-1){
g[i][j+len-1].emplace_back(len, cnt);
j=jump[j];
++cnt;
}
}
}
}
int dp(int l, int r){
if (l>r) return 0;
if (f[l][r]!=-1) return f[l][r];
int res=min(dp(l, r-1)+add, dp(l+1, r)+add);
for (auto &t:g[l][r]){
res=min(res, dp(l, l+t.first-1)+cut+t.second*paste+add*(r-l+1-t.second*t.first));
}
return f[l][r]=res;
}
void solve(){
memset(f, -1, sizeof f);
cin >> n >> s;
s=" "+s;
precalc();
cin >> add >> cut >> paste;
cout << dp(1, n);
}
int32_t main(){
#ifdef sus
freopen("cf.inp", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
197536 KB |
Output is correct |
2 |
Correct |
82 ms |
197836 KB |
Output is correct |
3 |
Correct |
80 ms |
197716 KB |
Output is correct |
4 |
Correct |
78 ms |
197672 KB |
Output is correct |
5 |
Correct |
54 ms |
197712 KB |
Output is correct |
6 |
Correct |
53 ms |
197712 KB |
Output is correct |
7 |
Correct |
52 ms |
197604 KB |
Output is correct |
8 |
Correct |
52 ms |
197712 KB |
Output is correct |
9 |
Correct |
52 ms |
197712 KB |
Output is correct |
10 |
Correct |
53 ms |
197712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
197712 KB |
Output is correct |
2 |
Correct |
51 ms |
197724 KB |
Output is correct |
3 |
Correct |
1763 ms |
458040 KB |
Output is correct |
4 |
Correct |
1917 ms |
505504 KB |
Output is correct |
5 |
Correct |
2226 ms |
561180 KB |
Output is correct |
6 |
Correct |
2634 ms |
627104 KB |
Output is correct |
7 |
Execution timed out |
3088 ms |
705368 KB |
Time limit exceeded |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
197536 KB |
Output is correct |
2 |
Correct |
82 ms |
197836 KB |
Output is correct |
3 |
Correct |
80 ms |
197716 KB |
Output is correct |
4 |
Correct |
78 ms |
197672 KB |
Output is correct |
5 |
Correct |
54 ms |
197712 KB |
Output is correct |
6 |
Correct |
53 ms |
197712 KB |
Output is correct |
7 |
Correct |
52 ms |
197604 KB |
Output is correct |
8 |
Correct |
52 ms |
197712 KB |
Output is correct |
9 |
Correct |
52 ms |
197712 KB |
Output is correct |
10 |
Correct |
53 ms |
197712 KB |
Output is correct |
11 |
Correct |
54 ms |
197716 KB |
Output is correct |
12 |
Correct |
52 ms |
197716 KB |
Output is correct |
13 |
Correct |
51 ms |
197716 KB |
Output is correct |
14 |
Correct |
56 ms |
197724 KB |
Output is correct |
15 |
Correct |
50 ms |
197784 KB |
Output is correct |
16 |
Correct |
50 ms |
197724 KB |
Output is correct |
17 |
Correct |
51 ms |
197584 KB |
Output is correct |
18 |
Correct |
50 ms |
197772 KB |
Output is correct |
19 |
Correct |
51 ms |
197968 KB |
Output is correct |
20 |
Correct |
51 ms |
197648 KB |
Output is correct |
21 |
Correct |
51 ms |
197716 KB |
Output is correct |
22 |
Correct |
50 ms |
197792 KB |
Output is correct |
23 |
Correct |
53 ms |
197716 KB |
Output is correct |
24 |
Correct |
51 ms |
197776 KB |
Output is correct |
25 |
Correct |
50 ms |
197724 KB |
Output is correct |
26 |
Correct |
55 ms |
197972 KB |
Output is correct |
27 |
Correct |
52 ms |
197800 KB |
Output is correct |
28 |
Correct |
51 ms |
197712 KB |
Output is correct |
29 |
Correct |
54 ms |
197724 KB |
Output is correct |
30 |
Correct |
52 ms |
197596 KB |
Output is correct |
31 |
Correct |
52 ms |
197712 KB |
Output is correct |
32 |
Correct |
51 ms |
197688 KB |
Output is correct |
33 |
Correct |
51 ms |
197712 KB |
Output is correct |
34 |
Correct |
51 ms |
197716 KB |
Output is correct |
35 |
Correct |
56 ms |
197716 KB |
Output is correct |
36 |
Correct |
51 ms |
197712 KB |
Output is correct |
37 |
Correct |
52 ms |
197776 KB |
Output is correct |
38 |
Correct |
52 ms |
197784 KB |
Output is correct |
39 |
Correct |
51 ms |
197832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
197536 KB |
Output is correct |
2 |
Correct |
82 ms |
197836 KB |
Output is correct |
3 |
Correct |
80 ms |
197716 KB |
Output is correct |
4 |
Correct |
78 ms |
197672 KB |
Output is correct |
5 |
Correct |
54 ms |
197712 KB |
Output is correct |
6 |
Correct |
53 ms |
197712 KB |
Output is correct |
7 |
Correct |
52 ms |
197604 KB |
Output is correct |
8 |
Correct |
52 ms |
197712 KB |
Output is correct |
9 |
Correct |
52 ms |
197712 KB |
Output is correct |
10 |
Correct |
53 ms |
197712 KB |
Output is correct |
11 |
Correct |
54 ms |
197716 KB |
Output is correct |
12 |
Correct |
52 ms |
197716 KB |
Output is correct |
13 |
Correct |
51 ms |
197716 KB |
Output is correct |
14 |
Correct |
56 ms |
197724 KB |
Output is correct |
15 |
Correct |
50 ms |
197784 KB |
Output is correct |
16 |
Correct |
50 ms |
197724 KB |
Output is correct |
17 |
Correct |
51 ms |
197584 KB |
Output is correct |
18 |
Correct |
50 ms |
197772 KB |
Output is correct |
19 |
Correct |
51 ms |
197968 KB |
Output is correct |
20 |
Correct |
51 ms |
197648 KB |
Output is correct |
21 |
Correct |
51 ms |
197716 KB |
Output is correct |
22 |
Correct |
50 ms |
197792 KB |
Output is correct |
23 |
Correct |
53 ms |
197716 KB |
Output is correct |
24 |
Correct |
51 ms |
197776 KB |
Output is correct |
25 |
Correct |
50 ms |
197724 KB |
Output is correct |
26 |
Correct |
55 ms |
197972 KB |
Output is correct |
27 |
Correct |
52 ms |
197800 KB |
Output is correct |
28 |
Correct |
51 ms |
197712 KB |
Output is correct |
29 |
Correct |
54 ms |
197724 KB |
Output is correct |
30 |
Correct |
52 ms |
197596 KB |
Output is correct |
31 |
Correct |
52 ms |
197712 KB |
Output is correct |
32 |
Correct |
51 ms |
197688 KB |
Output is correct |
33 |
Correct |
51 ms |
197712 KB |
Output is correct |
34 |
Correct |
51 ms |
197716 KB |
Output is correct |
35 |
Correct |
56 ms |
197716 KB |
Output is correct |
36 |
Correct |
51 ms |
197712 KB |
Output is correct |
37 |
Correct |
52 ms |
197776 KB |
Output is correct |
38 |
Correct |
52 ms |
197784 KB |
Output is correct |
39 |
Correct |
51 ms |
197832 KB |
Output is correct |
40 |
Correct |
52 ms |
197876 KB |
Output is correct |
41 |
Correct |
59 ms |
200016 KB |
Output is correct |
42 |
Correct |
62 ms |
198224 KB |
Output is correct |
43 |
Correct |
55 ms |
197968 KB |
Output is correct |
44 |
Correct |
55 ms |
197716 KB |
Output is correct |
45 |
Correct |
55 ms |
197716 KB |
Output is correct |
46 |
Correct |
55 ms |
197832 KB |
Output is correct |
47 |
Correct |
56 ms |
198488 KB |
Output is correct |
48 |
Correct |
57 ms |
197840 KB |
Output is correct |
49 |
Correct |
55 ms |
197972 KB |
Output is correct |
50 |
Correct |
55 ms |
198068 KB |
Output is correct |
51 |
Correct |
57 ms |
198736 KB |
Output is correct |
52 |
Correct |
56 ms |
198484 KB |
Output is correct |
53 |
Correct |
55 ms |
197712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
197536 KB |
Output is correct |
2 |
Correct |
82 ms |
197836 KB |
Output is correct |
3 |
Correct |
80 ms |
197716 KB |
Output is correct |
4 |
Correct |
78 ms |
197672 KB |
Output is correct |
5 |
Correct |
54 ms |
197712 KB |
Output is correct |
6 |
Correct |
53 ms |
197712 KB |
Output is correct |
7 |
Correct |
52 ms |
197604 KB |
Output is correct |
8 |
Correct |
52 ms |
197712 KB |
Output is correct |
9 |
Correct |
52 ms |
197712 KB |
Output is correct |
10 |
Correct |
53 ms |
197712 KB |
Output is correct |
11 |
Correct |
54 ms |
197716 KB |
Output is correct |
12 |
Correct |
52 ms |
197716 KB |
Output is correct |
13 |
Correct |
51 ms |
197716 KB |
Output is correct |
14 |
Correct |
56 ms |
197724 KB |
Output is correct |
15 |
Correct |
50 ms |
197784 KB |
Output is correct |
16 |
Correct |
50 ms |
197724 KB |
Output is correct |
17 |
Correct |
51 ms |
197584 KB |
Output is correct |
18 |
Correct |
50 ms |
197772 KB |
Output is correct |
19 |
Correct |
51 ms |
197968 KB |
Output is correct |
20 |
Correct |
51 ms |
197648 KB |
Output is correct |
21 |
Correct |
51 ms |
197716 KB |
Output is correct |
22 |
Correct |
50 ms |
197792 KB |
Output is correct |
23 |
Correct |
53 ms |
197716 KB |
Output is correct |
24 |
Correct |
51 ms |
197776 KB |
Output is correct |
25 |
Correct |
50 ms |
197724 KB |
Output is correct |
26 |
Correct |
55 ms |
197972 KB |
Output is correct |
27 |
Correct |
52 ms |
197800 KB |
Output is correct |
28 |
Correct |
51 ms |
197712 KB |
Output is correct |
29 |
Correct |
54 ms |
197724 KB |
Output is correct |
30 |
Correct |
52 ms |
197596 KB |
Output is correct |
31 |
Correct |
52 ms |
197712 KB |
Output is correct |
32 |
Correct |
51 ms |
197688 KB |
Output is correct |
33 |
Correct |
51 ms |
197712 KB |
Output is correct |
34 |
Correct |
51 ms |
197716 KB |
Output is correct |
35 |
Correct |
56 ms |
197716 KB |
Output is correct |
36 |
Correct |
51 ms |
197712 KB |
Output is correct |
37 |
Correct |
52 ms |
197776 KB |
Output is correct |
38 |
Correct |
52 ms |
197784 KB |
Output is correct |
39 |
Correct |
51 ms |
197832 KB |
Output is correct |
40 |
Correct |
52 ms |
197876 KB |
Output is correct |
41 |
Correct |
59 ms |
200016 KB |
Output is correct |
42 |
Correct |
62 ms |
198224 KB |
Output is correct |
43 |
Correct |
55 ms |
197968 KB |
Output is correct |
44 |
Correct |
55 ms |
197716 KB |
Output is correct |
45 |
Correct |
55 ms |
197716 KB |
Output is correct |
46 |
Correct |
55 ms |
197832 KB |
Output is correct |
47 |
Correct |
56 ms |
198488 KB |
Output is correct |
48 |
Correct |
57 ms |
197840 KB |
Output is correct |
49 |
Correct |
55 ms |
197972 KB |
Output is correct |
50 |
Correct |
55 ms |
198068 KB |
Output is correct |
51 |
Correct |
57 ms |
198736 KB |
Output is correct |
52 |
Correct |
56 ms |
198484 KB |
Output is correct |
53 |
Correct |
55 ms |
197712 KB |
Output is correct |
54 |
Correct |
74 ms |
200272 KB |
Output is correct |
55 |
Correct |
499 ms |
269532 KB |
Output is correct |
56 |
Correct |
181 ms |
211280 KB |
Output is correct |
57 |
Correct |
169 ms |
205500 KB |
Output is correct |
58 |
Correct |
149 ms |
201000 KB |
Output is correct |
59 |
Correct |
145 ms |
199252 KB |
Output is correct |
60 |
Correct |
165 ms |
198740 KB |
Output is correct |
61 |
Correct |
160 ms |
208952 KB |
Output is correct |
62 |
Correct |
414 ms |
257872 KB |
Output is correct |
63 |
Correct |
157 ms |
205652 KB |
Output is correct |
64 |
Correct |
178 ms |
209992 KB |
Output is correct |
65 |
Correct |
351 ms |
232548 KB |
Output is correct |
66 |
Correct |
369 ms |
232488 KB |
Output is correct |
67 |
Correct |
144 ms |
198480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
197536 KB |
Output is correct |
2 |
Correct |
82 ms |
197836 KB |
Output is correct |
3 |
Correct |
80 ms |
197716 KB |
Output is correct |
4 |
Correct |
78 ms |
197672 KB |
Output is correct |
5 |
Correct |
54 ms |
197712 KB |
Output is correct |
6 |
Correct |
53 ms |
197712 KB |
Output is correct |
7 |
Correct |
52 ms |
197604 KB |
Output is correct |
8 |
Correct |
52 ms |
197712 KB |
Output is correct |
9 |
Correct |
52 ms |
197712 KB |
Output is correct |
10 |
Correct |
53 ms |
197712 KB |
Output is correct |
11 |
Correct |
51 ms |
197712 KB |
Output is correct |
12 |
Correct |
51 ms |
197724 KB |
Output is correct |
13 |
Correct |
1763 ms |
458040 KB |
Output is correct |
14 |
Correct |
1917 ms |
505504 KB |
Output is correct |
15 |
Correct |
2226 ms |
561180 KB |
Output is correct |
16 |
Correct |
2634 ms |
627104 KB |
Output is correct |
17 |
Execution timed out |
3088 ms |
705368 KB |
Time limit exceeded |
18 |
Halted |
0 ms |
0 KB |
- |