#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)
const int N=2510;
int f[N][N], add, cut, paste, n;
int g[N][N];
string s;
void precalc(){
for (int t=1; t<=n; ++t){
map<string, int> mp;
for (int r=t; r<=n; ++r){
string s1=s.substr(r-t+1, t);
g[r][t]=mp.count(s1)?mp[s1]:-1;
if (r-t+1>=t){
string s2=s.substr(r-t+1-t+1, t);
mp[s2]=r-t+1;
}
}
}
}
int count(int l, int r, int t){
if (r-l+1<t) return 0;
int pos=g[r][t];
return count(l, pos, t)+1;
}
int dp(int l, int r){
if (l>r) return 0;
if (f[l][r]!=-1) return f[l][r];
int res=dp(l, r-1)+add;
for (int t=l; t<=r; ++t){
int cnt=count(l, r, r-t+1);
if (cnt!=1) res=min(res, dp(t, r)+cut+cnt*paste+add*(r-l+1-cnt*(r-t+1)));
}
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(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int ntests=1;
// cin >> ntests;
for (int i=1; i<=ntests; ++i) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
51544 KB |
Output is correct |
2 |
Correct |
16 ms |
51544 KB |
Output is correct |
3 |
Correct |
16 ms |
51548 KB |
Output is correct |
4 |
Correct |
18 ms |
51548 KB |
Output is correct |
5 |
Correct |
18 ms |
51548 KB |
Output is correct |
6 |
Correct |
18 ms |
51720 KB |
Output is correct |
7 |
Correct |
17 ms |
51568 KB |
Output is correct |
8 |
Correct |
17 ms |
51548 KB |
Output is correct |
9 |
Correct |
17 ms |
51548 KB |
Output is correct |
10 |
Correct |
17 ms |
51704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
51548 KB |
Output is correct |
2 |
Correct |
17 ms |
51712 KB |
Output is correct |
3 |
Execution timed out |
3045 ms |
72196 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
51544 KB |
Output is correct |
2 |
Correct |
16 ms |
51544 KB |
Output is correct |
3 |
Correct |
16 ms |
51548 KB |
Output is correct |
4 |
Correct |
18 ms |
51548 KB |
Output is correct |
5 |
Correct |
18 ms |
51548 KB |
Output is correct |
6 |
Correct |
18 ms |
51720 KB |
Output is correct |
7 |
Correct |
17 ms |
51568 KB |
Output is correct |
8 |
Correct |
17 ms |
51548 KB |
Output is correct |
9 |
Correct |
17 ms |
51548 KB |
Output is correct |
10 |
Correct |
17 ms |
51704 KB |
Output is correct |
11 |
Correct |
17 ms |
51548 KB |
Output is correct |
12 |
Correct |
16 ms |
51548 KB |
Output is correct |
13 |
Correct |
16 ms |
51548 KB |
Output is correct |
14 |
Correct |
18 ms |
51544 KB |
Output is correct |
15 |
Correct |
17 ms |
51804 KB |
Output is correct |
16 |
Correct |
17 ms |
51720 KB |
Output is correct |
17 |
Correct |
17 ms |
51548 KB |
Output is correct |
18 |
Correct |
17 ms |
51544 KB |
Output is correct |
19 |
Correct |
17 ms |
51548 KB |
Output is correct |
20 |
Correct |
17 ms |
51544 KB |
Output is correct |
21 |
Correct |
17 ms |
51804 KB |
Output is correct |
22 |
Correct |
18 ms |
51804 KB |
Output is correct |
23 |
Correct |
17 ms |
51620 KB |
Output is correct |
24 |
Correct |
17 ms |
51800 KB |
Output is correct |
25 |
Correct |
18 ms |
51692 KB |
Output is correct |
26 |
Correct |
19 ms |
51756 KB |
Output is correct |
27 |
Correct |
17 ms |
51800 KB |
Output is correct |
28 |
Correct |
17 ms |
51804 KB |
Output is correct |
29 |
Correct |
17 ms |
51800 KB |
Output is correct |
30 |
Correct |
18 ms |
51804 KB |
Output is correct |
31 |
Correct |
17 ms |
51600 KB |
Output is correct |
32 |
Correct |
18 ms |
51724 KB |
Output is correct |
33 |
Correct |
17 ms |
51804 KB |
Output is correct |
34 |
Correct |
17 ms |
51596 KB |
Output is correct |
35 |
Correct |
17 ms |
51632 KB |
Output is correct |
36 |
Correct |
17 ms |
51676 KB |
Output is correct |
37 |
Correct |
17 ms |
51712 KB |
Output is correct |
38 |
Correct |
17 ms |
51548 KB |
Output is correct |
39 |
Correct |
17 ms |
51800 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
51544 KB |
Output is correct |
2 |
Correct |
16 ms |
51544 KB |
Output is correct |
3 |
Correct |
16 ms |
51548 KB |
Output is correct |
4 |
Correct |
18 ms |
51548 KB |
Output is correct |
5 |
Correct |
18 ms |
51548 KB |
Output is correct |
6 |
Correct |
18 ms |
51720 KB |
Output is correct |
7 |
Correct |
17 ms |
51568 KB |
Output is correct |
8 |
Correct |
17 ms |
51548 KB |
Output is correct |
9 |
Correct |
17 ms |
51548 KB |
Output is correct |
10 |
Correct |
17 ms |
51704 KB |
Output is correct |
11 |
Correct |
17 ms |
51548 KB |
Output is correct |
12 |
Correct |
16 ms |
51548 KB |
Output is correct |
13 |
Correct |
16 ms |
51548 KB |
Output is correct |
14 |
Correct |
18 ms |
51544 KB |
Output is correct |
15 |
Correct |
17 ms |
51804 KB |
Output is correct |
16 |
Correct |
17 ms |
51720 KB |
Output is correct |
17 |
Correct |
17 ms |
51548 KB |
Output is correct |
18 |
Correct |
17 ms |
51544 KB |
Output is correct |
19 |
Correct |
17 ms |
51548 KB |
Output is correct |
20 |
Correct |
17 ms |
51544 KB |
Output is correct |
21 |
Correct |
17 ms |
51804 KB |
Output is correct |
22 |
Correct |
18 ms |
51804 KB |
Output is correct |
23 |
Correct |
17 ms |
51620 KB |
Output is correct |
24 |
Correct |
17 ms |
51800 KB |
Output is correct |
25 |
Correct |
18 ms |
51692 KB |
Output is correct |
26 |
Correct |
19 ms |
51756 KB |
Output is correct |
27 |
Correct |
17 ms |
51800 KB |
Output is correct |
28 |
Correct |
17 ms |
51804 KB |
Output is correct |
29 |
Correct |
17 ms |
51800 KB |
Output is correct |
30 |
Correct |
18 ms |
51804 KB |
Output is correct |
31 |
Correct |
17 ms |
51600 KB |
Output is correct |
32 |
Correct |
18 ms |
51724 KB |
Output is correct |
33 |
Correct |
17 ms |
51804 KB |
Output is correct |
34 |
Correct |
17 ms |
51596 KB |
Output is correct |
35 |
Correct |
17 ms |
51632 KB |
Output is correct |
36 |
Correct |
17 ms |
51676 KB |
Output is correct |
37 |
Correct |
17 ms |
51712 KB |
Output is correct |
38 |
Correct |
17 ms |
51548 KB |
Output is correct |
39 |
Correct |
17 ms |
51800 KB |
Output is correct |
40 |
Correct |
17 ms |
52060 KB |
Output is correct |
41 |
Correct |
22 ms |
52572 KB |
Output is correct |
42 |
Correct |
21 ms |
52636 KB |
Output is correct |
43 |
Correct |
21 ms |
52824 KB |
Output is correct |
44 |
Correct |
21 ms |
52648 KB |
Output is correct |
45 |
Correct |
21 ms |
52572 KB |
Output is correct |
46 |
Correct |
20 ms |
52572 KB |
Output is correct |
47 |
Correct |
21 ms |
52568 KB |
Output is correct |
48 |
Correct |
21 ms |
52572 KB |
Output is correct |
49 |
Correct |
21 ms |
52568 KB |
Output is correct |
50 |
Correct |
21 ms |
52568 KB |
Output is correct |
51 |
Correct |
21 ms |
52568 KB |
Output is correct |
52 |
Correct |
22 ms |
52572 KB |
Output is correct |
53 |
Correct |
21 ms |
52628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
51544 KB |
Output is correct |
2 |
Correct |
16 ms |
51544 KB |
Output is correct |
3 |
Correct |
16 ms |
51548 KB |
Output is correct |
4 |
Correct |
18 ms |
51548 KB |
Output is correct |
5 |
Correct |
18 ms |
51548 KB |
Output is correct |
6 |
Correct |
18 ms |
51720 KB |
Output is correct |
7 |
Correct |
17 ms |
51568 KB |
Output is correct |
8 |
Correct |
17 ms |
51548 KB |
Output is correct |
9 |
Correct |
17 ms |
51548 KB |
Output is correct |
10 |
Correct |
17 ms |
51704 KB |
Output is correct |
11 |
Correct |
17 ms |
51548 KB |
Output is correct |
12 |
Correct |
16 ms |
51548 KB |
Output is correct |
13 |
Correct |
16 ms |
51548 KB |
Output is correct |
14 |
Correct |
18 ms |
51544 KB |
Output is correct |
15 |
Correct |
17 ms |
51804 KB |
Output is correct |
16 |
Correct |
17 ms |
51720 KB |
Output is correct |
17 |
Correct |
17 ms |
51548 KB |
Output is correct |
18 |
Correct |
17 ms |
51544 KB |
Output is correct |
19 |
Correct |
17 ms |
51548 KB |
Output is correct |
20 |
Correct |
17 ms |
51544 KB |
Output is correct |
21 |
Correct |
17 ms |
51804 KB |
Output is correct |
22 |
Correct |
18 ms |
51804 KB |
Output is correct |
23 |
Correct |
17 ms |
51620 KB |
Output is correct |
24 |
Correct |
17 ms |
51800 KB |
Output is correct |
25 |
Correct |
18 ms |
51692 KB |
Output is correct |
26 |
Correct |
19 ms |
51756 KB |
Output is correct |
27 |
Correct |
17 ms |
51800 KB |
Output is correct |
28 |
Correct |
17 ms |
51804 KB |
Output is correct |
29 |
Correct |
17 ms |
51800 KB |
Output is correct |
30 |
Correct |
18 ms |
51804 KB |
Output is correct |
31 |
Correct |
17 ms |
51600 KB |
Output is correct |
32 |
Correct |
18 ms |
51724 KB |
Output is correct |
33 |
Correct |
17 ms |
51804 KB |
Output is correct |
34 |
Correct |
17 ms |
51596 KB |
Output is correct |
35 |
Correct |
17 ms |
51632 KB |
Output is correct |
36 |
Correct |
17 ms |
51676 KB |
Output is correct |
37 |
Correct |
17 ms |
51712 KB |
Output is correct |
38 |
Correct |
17 ms |
51548 KB |
Output is correct |
39 |
Correct |
17 ms |
51800 KB |
Output is correct |
40 |
Correct |
17 ms |
52060 KB |
Output is correct |
41 |
Correct |
22 ms |
52572 KB |
Output is correct |
42 |
Correct |
21 ms |
52636 KB |
Output is correct |
43 |
Correct |
21 ms |
52824 KB |
Output is correct |
44 |
Correct |
21 ms |
52648 KB |
Output is correct |
45 |
Correct |
21 ms |
52572 KB |
Output is correct |
46 |
Correct |
20 ms |
52572 KB |
Output is correct |
47 |
Correct |
21 ms |
52568 KB |
Output is correct |
48 |
Correct |
21 ms |
52572 KB |
Output is correct |
49 |
Correct |
21 ms |
52568 KB |
Output is correct |
50 |
Correct |
21 ms |
52568 KB |
Output is correct |
51 |
Correct |
21 ms |
52568 KB |
Output is correct |
52 |
Correct |
22 ms |
52572 KB |
Output is correct |
53 |
Correct |
21 ms |
52628 KB |
Output is correct |
54 |
Correct |
34 ms |
54356 KB |
Output is correct |
55 |
Correct |
1008 ms |
59784 KB |
Output is correct |
56 |
Correct |
118 ms |
59956 KB |
Output is correct |
57 |
Correct |
118 ms |
60000 KB |
Output is correct |
58 |
Correct |
115 ms |
59836 KB |
Output is correct |
59 |
Correct |
115 ms |
59912 KB |
Output is correct |
60 |
Correct |
113 ms |
59984 KB |
Output is correct |
61 |
Correct |
165 ms |
59732 KB |
Output is correct |
62 |
Correct |
584 ms |
59808 KB |
Output is correct |
63 |
Correct |
144 ms |
59812 KB |
Output is correct |
64 |
Correct |
145 ms |
60036 KB |
Output is correct |
65 |
Correct |
271 ms |
59936 KB |
Output is correct |
66 |
Correct |
267 ms |
59984 KB |
Output is correct |
67 |
Correct |
115 ms |
59976 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
51544 KB |
Output is correct |
2 |
Correct |
16 ms |
51544 KB |
Output is correct |
3 |
Correct |
16 ms |
51548 KB |
Output is correct |
4 |
Correct |
18 ms |
51548 KB |
Output is correct |
5 |
Correct |
18 ms |
51548 KB |
Output is correct |
6 |
Correct |
18 ms |
51720 KB |
Output is correct |
7 |
Correct |
17 ms |
51568 KB |
Output is correct |
8 |
Correct |
17 ms |
51548 KB |
Output is correct |
9 |
Correct |
17 ms |
51548 KB |
Output is correct |
10 |
Correct |
17 ms |
51704 KB |
Output is correct |
11 |
Correct |
17 ms |
51548 KB |
Output is correct |
12 |
Correct |
17 ms |
51712 KB |
Output is correct |
13 |
Execution timed out |
3045 ms |
72196 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |