QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#251617 | #2273. Suffixes may Contain Prefixes | lemonilemon# | AC ✓ | 214ms | 19840kb | C++17 | 1.8kb | 2023-11-14 21:54:39 | 2023-11-14 21:54:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using uint = unsigned int;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 46 * ll(1e17);
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 25;
vector<int> kmp(const string &s) {
int n = s.size();
vector<int> dp(n);
for (int i = 1, j = 0; i < n; i++) {
while (j && s[i] != s[j])
j = dp[j - 1];
if (s[i] == s[j])
j++;
dp[i] = j;
}
return dp;
}
const int N = 2007;
int dp[N][N];
signed main() { ios::sync_with_stdio(0); cin.tie(0);
string s;
int n;
cin >> s >> n;
auto k = kmp(s);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
dp[i][j] = -INF;
dp[0][0] = 0;
vector<int> dep(s.size() + 1);
vector<vector<int>> nxt(s.size() + 1, vector<int>(26));
dep[1] = 1;
for (int i = 2; i <= s.size(); i++)
dep[i] = dep[k[i - 1]] + 1;
for (int i = 0; i <= s.size(); i++) {
for (int j = 0; j < 26; j++) {
int nxt_cal = i;
if (nxt_cal == s.size())
nxt_cal = k[nxt_cal - 1];
while (nxt_cal && s[nxt_cal] != j + 'a')
nxt_cal = k[nxt_cal - 1];
if (s[nxt_cal] == j + 'a')
nxt_cal++;
nxt[i][j] = nxt_cal;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dp[i][j] < 0)
continue;
//cerr << i << ' ' << j << ' ' << dp[i][j] << '\n';
for (int c = 0; c < 26; c++)
dp[i + 1][nxt[j][c]] = max(dp[i + 1][nxt[j][c]], dp[i][j] + dep[nxt[j][c]]);
}
}
int mx = 0;
for (int i = 0; i <= n; i++)
mx = max(mx, dp[n][i]);
cout << mx << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 19592kb
input:
fsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfsfsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfsfsfffsfffssfsfffsfsf...
output:
852
result:
ok single line: '852'
Test #2:
score: 0
Accepted
time: 36ms
memory: 19364kb
input:
ddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttddddddttddttddttddddtdddttddttddttdddddttddttddtddttddttddttddddtdddttddttddttdddddttddttddttddttddttddttddddtdddttddttddttdddddttddttddt...
output:
5894
result:
ok single line: '5894'
Test #3:
score: 0
Accepted
time: 107ms
memory: 19836kb
input:
wswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswswswwwsswswswwwswswswwwswswsswswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswwswswwwswswswwwsswswswwwswswswwwswswwwswswswwwsswswswwwswswssswwswwswswwwswsws...
output:
10500
result:
ok single line: '10500'
Test #4:
score: 0
Accepted
time: 22ms
memory: 19620kb
input:
sjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjsspffsjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsjssjssjsspffsjsspfsjsspffsjssjsspffsjsspfsjsspffsjsspsjsspffsjsspfsjsspffsjssjfsjsspffsjsspfsjsspffsj...
output:
4267
result:
ok single line: '4267'
Test #5:
score: 0
Accepted
time: 113ms
memory: 19500kb
input:
mmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpmmpmmmpmmpmpmmpmmmppmmpmmmpmmpmpfmzmmpmmmmmpmmmmmpmmmmpmmmpmmpmpfmzmmpmmmmmpfqmmpmmmpmmpmpfmzmmpmmmmmpmmmpmmpmpm...
output:
9536
result:
ok single line: '9536'
Test #6:
score: 0
Accepted
time: 22ms
memory: 19616kb
input:
pepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepepypgakpepypopepepypopepypopepepyzpepypopepepypepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepypopepepypopepypopepvplpepypopepepypopepypopepepyzpepypopepepypoperpepypopepepypopepypopepepyzpepypopepep...
output:
4033
result:
ok single line: '4033'
Test #7:
score: 0
Accepted
time: 107ms
memory: 19604kb
input:
fifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfyqnfifuurfifuugfifuurfifufifuurfifuugfifuurxvfifuurfifuugfifuurfifufifuurfifuugfifuurfifuefifuurfifuugfifuurfifufifuurfifuugfiffifuurfifuu...
output:
9452
result:
ok single line: '9452'
Test #8:
score: 0
Accepted
time: 20ms
memory: 19592kb
input:
gwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgxlggwcgwgxrgwgxlggwgxihdggwgxlggwcgwgxlgwgxlmgwgxlgwgxlggwgxihdggwgxlggwcgwtxgwgxlggwgxihdggwgwvgwgxlggwgxihdggw...
output:
3584
result:
ok single line: '3584'
Test #9:
score: 0
Accepted
time: 0ms
memory: 19332kb
input:
aabaacaabaa 101
output:
249
result:
ok single line: '249'
Test #10:
score: 0
Accepted
time: 0ms
memory: 19540kb
input:
aabaacaabaa 102
output:
251
result:
ok single line: '251'
Test #11:
score: 0
Accepted
time: 3ms
memory: 19512kb
input:
aabaacaabaa 103
output:
253
result:
ok single line: '253'
Test #12:
score: 0
Accepted
time: 0ms
memory: 19340kb
input:
aabaacaabaa 104
output:
255
result:
ok single line: '255'
Test #13:
score: 0
Accepted
time: 0ms
memory: 19260kb
input:
aabaacaabaa 105
output:
257
result:
ok single line: '257'
Test #14:
score: 0
Accepted
time: 5ms
memory: 19352kb
input:
cciccpccicc 2000
output:
4995
result:
ok single line: '4995'
Test #15:
score: 0
Accepted
time: 0ms
memory: 19332kb
input:
lkultxuuxtkltukllulxkltuutkuuttkuxutuuxuutuxtkxktklltllulkltxtttkkkxxtuxltkxtxtttlltttlkkkutkkuxulklxuuxullkkxtktlxtutuxlktkkllxutlllxkltkutxltxtlluxxlxxxklxlluuxllllxxlllluktkxtkutluktxkkukluktkkuktlkkultukulxlxkltlllkkluluutkxlxkuktktxxtkkkkkuxtxttkxtuxkkttklltulktltxkutluuulluxtuxlllltlutxulxxltk...
output:
1
result:
ok single line: '1'
Test #16:
score: 0
Accepted
time: 4ms
memory: 19612kb
input:
zrszgeggmmagjcibhsuuugohqppnncuuksrynidfbmhaqpnzswblenhttvtgadwjybijjwhixqppgzqajdqbmjrgaziljastkonutvyqrxtvshhoidkixodyrekyshlafxnikbgaqegxbgwmpgbxnpkdxhnhcocmbpimftogrlydyqitekbfvtimiztujfejkomujzztadjhrvdqlakxnbctuaubumwlwyibmyjabrrdznkvndghplgqjmcvqhmgbsrnpmjjbkkqmnvzczlpsrgdmsmmcgksbkhzatnpiwch...
output:
2
result:
ok single line: '2'
Test #17:
score: 0
Accepted
time: 9ms
memory: 19280kb
input:
xxiiixxhhhxxiiixx 1996
output:
4187
result:
ok single line: '4187'
Test #18:
score: 0
Accepted
time: 4ms
memory: 19516kb
input:
xxiiixxhhhxxiiixx 1997
output:
4190
result:
ok single line: '4190'
Test #19:
score: 0
Accepted
time: 8ms
memory: 19288kb
input:
xxiiixxhhhxxiiixx 1998
output:
4192
result:
ok single line: '4192'
Test #20:
score: 0
Accepted
time: 5ms
memory: 19256kb
input:
xxiiixxhhhxxiiixx 1999
output:
4194
result:
ok single line: '4194'
Test #21:
score: 0
Accepted
time: 4ms
memory: 19320kb
input:
xxiiixxhhhxxiiixx 2000
output:
4196
result:
ok single line: '4196'
Test #22:
score: 0
Accepted
time: 7ms
memory: 19220kb
input:
xxiiixxhhhxxiiixxicpcicpc 2000
output:
4196
result:
ok single line: '4196'
Test #23:
score: 0
Accepted
time: 0ms
memory: 19252kb
input:
c 123
output:
123
result:
ok single line: '123'
Test #24:
score: 0
Accepted
time: 7ms
memory: 19260kb
input:
p 2000
output:
2000
result:
ok single line: '2000'
Test #25:
score: 0
Accepted
time: 3ms
memory: 19360kb
input:
nananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananananana 500
output:
40100
result:
ok single line: '40100'
Test #26:
score: 0
Accepted
time: 35ms
memory: 19764kb
input:
czgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczgczg...
output:
1717
result:
ok single line: '1717'
Test #27:
score: 0
Accepted
time: 117ms
memory: 19612kb
input:
fjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxxfjlpvbnxxx...
output:
201000
result:
ok single line: '201000'
Test #28:
score: 0
Accepted
time: 116ms
memory: 19840kb
input:
uuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxppuuarrprirpprxpp...
output:
134469
result:
ok single line: '134469'
Test #29:
score: 0
Accepted
time: 40ms
memory: 19352kb
input:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
440469
result:
ok single line: '440469'
Test #30:
score: 0
Accepted
time: 214ms
memory: 19500kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
2001000
result:
ok single line: '2001000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 19344kb
input:
a 1
output:
1
result:
ok single line: '1'
Test #32:
score: 0
Accepted
time: 0ms
memory: 19336kb
input:
z 1
output:
1
result:
ok single line: '1'
Test #33:
score: 0
Accepted
time: 2ms
memory: 19544kb
input:
cc 1
output:
1
result:
ok single line: '1'
Test #34:
score: 0
Accepted
time: 0ms
memory: 19340kb
input:
gg 1
output:
1
result:
ok single line: '1'
Test #35:
score: 0
Accepted
time: 4ms
memory: 19220kb
input:
yx 2
output:
2
result:
ok single line: '2'
Test #36:
score: 0
Accepted
time: 0ms
memory: 19476kb
input:
tr 2
output:
2
result:
ok single line: '2'
Test #37:
score: 0
Accepted
time: 0ms
memory: 19548kb
input:
xxyxxyx 20
output:
49
result:
ok single line: '49'