QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#870610 | #9514. 研心 | NineSuns | 20 | 4861ms | 31756kb | C++14 | 807b | 2025-01-25 17:02:36 | 2025-01-25 17:02:42 |
Judging History
answer
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 4e5+5, B = 200;
int n, m;
string a[N], b[N];
int f[N], r[N];
int gmax (string s) {
int res = 1;
r[0] = 1;
for (int i = 1, j = 0, mr = 0;i < s.size();i++) {
r[i] = 0;
if (mr >= i) r[i] = min(r[j+j-i], mr-i+1);
while (i-r[i] >= 0 && i+r[i] < s.size() && s[i-r[i]] == s[i+r[i]]) r[i]++;
if (i+r[i]-1 > mr) mr = i+r[i]-1, j = i;
res = max(res, r[i]);
}
return res;
}
int main () {
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= m;i++) cin >> b[i];
ll ans = 0;
for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) ans += gmax(a[i]+b[j]);
cout << ans;
return 0;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 6ms
memory: 30348kb
input:
10 100 aabaababaaaababbabaaaababaababbbaabbbaabaabaabbbaababaaababbaababababbbaababbbbbbbbaabbbbaabbbbbbbbaabaabbbaabbbbbabbbbbaabbbaabaa bbaaabaabbbbaaabaaaaabbbbbabaabbabbaabbaabbaabbabbababaabaabbaabbbbbbaaaabbbbabaaaabaaabbbabaaaaaabbaaaabbbabbbbbaaaabbabaababbaabbaaabbbbbbaaaabbbababaabbaaaba b...
output:
10468
result:
ok single line: '10468'
Test #2:
score: 20
Accepted
time: 4ms
memory: 28880kb
input:
10 100 abbacbbaabababcaabbaabbbabcaccabcabbabbbccaacabaabacccbacaaabbaaabbbaacaabbabcabbbcbacaaaaabaaaabaaacbbccbacacbbaaccacbabcbccacbaaacaaacccbabbaccacaaacaabbbccaaccbbabaabcbbcbcbb bccabcacbacccbcababaccccaaabbccacaccccabbaabbcacabaccabacbbbaaaabaabccbcaacaaccbcacabcbbbcccccabccbaababccccabcabab...
output:
6384
result:
ok single line: '6384'
Test #3:
score: 20
Accepted
time: 5ms
memory: 30200kb
input:
50 50 aaaaabbabbbbbaababbaaaababaababababbbbaabaaaaaaaabaabbaaabaaaabaaabaabbbabbbababbbbabbbabbaaababbabaabbabbabbabbaaababaaaaabbbbbbaabaabaabbbbbabaaababb abbabbbaabaaaaabababaabbabaabbbbab bababbbbaabaabbaabbbbaabaabbbaabbbbaaabbabbbaaabbbbaaabaabbaaaaaabbbabaaaaabbaabaabaaabaaababbbbbaaabbbbbba...
output:
21362
result:
ok single line: '21362'
Test #4:
score: 20
Accepted
time: 4ms
memory: 29768kb
input:
50 50 aababcabbbcbaacaaaaccababbacbbaaabcbaaccabbababbcccaacaaaacacbcbaaabaacabbbbbbaccaaacbbacaacacbcccbbacabbcbcbacababcbbacaccaacacbcccbababaccabccccbabaccababccccbcbabcabcabccaaccababcbccacbbaaaacc cbaccababccbaaacbccabbcccacacacaaaabaaababcacabaccbccacbcbaaaaabbacbbaccabba ccbcbcacbcaccabbbccaa...
output:
13421
result:
ok single line: '13421'
Test #5:
score: 20
Accepted
time: 86ms
memory: 30452kb
input:
1000 1000 a aabbab bbbbababbbba bb baaaaa ba a baa a bbaaaabaaaba ba a a a bbababbbbbb b aaabb bbbbbaabbabab bbaaa aaaa aa aaaaaababb a bbaba baaa aabbab babaab b aab bbbabb aaaabbbbbaaaaaa bbbbbbbaabab bb ab aaa aaababb babaaaabab aa aaabaaababa abbabaaaaabb bbaa abaabb baa abba aaaa abbbb aab b aa...
output:
3159935
result:
ok single line: '3159935'
Subtask #2:
score: 0
Time Limit Exceeded
Test #6:
score: 0
Time Limit Exceeded
input:
1 10000 bcacacbcdadbcbccbdddaaddabcaccccbaabbcdcdaabdacccadacbbbabdaaacadacdccadcbdadadcaaabdbdbdcdcccbacbdbccacbdadcaaaacbabdadcacdcacadcadaabdaaabccccdcbcdbcadcaabbbaacaadaccdaccadbddcdbccbcddcaadcaadaadbbaadbcdbddbcbadbccbaddaacabcdccbadaddcadcbababccabcaadbcbdbcbbcdcbdbcdbdaaddbacddcabbbdccbddba...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #12:
score: 20
Accepted
time: 2756ms
memory: 31756kb
input:
100 1000 abbabbbbabbbbabaabaabbbbabaaabbbaabaabbabaabaabbaabbaabbababbabbababbbaabaabbaabbbabaabbbaaaabaaaabaababbaaaaaaaaabaabbaababbbbbbabbbabbbbababbbaaaaaabaaaabaaabbabbaaaaabbbabbabaabbabababbaaababbbaaaabbabbbabbabbabbbbbbabaabaabbbaabaaabbaabbabbbbaabbabaaabaabaabbbabbbbbabaababbbabababaabbba...
output:
1289287
result:
ok single line: '1289287'
Test #13:
score: 20
Accepted
time: 4861ms
memory: 30080kb
input:
1000 1000 babbbabaabaaaabbbbbababaaabbaabbbbbabbaababbbbaaabbbbaaabbbababbaaaabaaabbbbbbbbaabbabbbabbabbaaabaabbbbbbbababaabbbbabaaabbaaaaabbbaababbaaaaabbbbaaaabbbaabaaababaaabbabbbabbabbbabbaabbabbbabaaaaaabaabbabbababbbbbabaaabbbbababbbaabbbaaabbababaababbbbbaaabbbabbabaaaababbbaabaaaabbbabaaabbb...
output:
10431998
result:
ok single line: '10431998'
Test #14:
score: 0
Time Limit Exceeded
input:
1000 10000 babbababbbaaaaaaaaababbabbbababbbbbbbbabaaaaaabbaababbbbbbbaaaabbaaaaabbbbbbbababbabaaaaabbaaabaaaaaaabbbabbabbaaabbbabbbbababababbabbababbabbbbaabbbbaababbaababbababbbaaabbbbaaabaaaabababbbbaabaababbabbbaabbbbbabbbaaabaabaabbaabaaaaabbabbbbaaabbabbbaababbbaabaaaabbbababbbbbbbabababbaabab...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #17:
score: 30
Accepted
time: 2675ms
memory: 30524kb
input:
100 1000 bcbccabbbabacabaabbccbaaabbbbcbbbaaaacaaabbccbababbacbbabbbaccccccccbccabcaacbbccbbbbcaaacabcccaccbaacccbcbaaaccbcaaaaaaaabccaaaacccbabacbcababbacbbbcaabaaacbbcaccbaccccbbcbacabaacbcaccacbcbcbbcbccccbbcacccaabbabcaabbacabaaacccbbcbccbabbcbccbcbbbabbaabacbccbacababbacbababbbaacccacbabcabcaba...
output:
833103
result:
ok single line: '833103'
Test #18:
score: 30
Accepted
time: 4680ms
memory: 31688kb
input:
1000 1000 cacccababcaaccbaaabcbcabcbbccbcbcbbcacbbcabcaaccabcccaacabccaacaaaababbbbbcbbcbcbbbcacbaabccaccbaacaaacabbbcbcbaabbcccacaababbbabcaabbaabaabaabaabccaacccbabcbaacccbbbccaacbbacacacaacccbcbcbaccbccaaacabaacbcbaacbcbacaccbacbbcaccbabbbabbbaccccbbbcacccccaacbbaaaccacabaaacaccabacacbaaaaacbacab...
output:
6757759
result:
ok single line: '6757759'
Test #19:
score: 0
Time Limit Exceeded
input:
1000 10000 cbacbccbcbbcccbbcccaacccbbbacbccaaaccabacaabacccbbbcbabcaacabbabbabcaaaabccbabcaaacaaabbbacccacabcacccaaababcacbaacaccbccbcaaaaaaaaccabbcaaaaabccacaacbccabacabcccaabbcaccbcabbccbabbbccaacbabcbacacabbaaaababbccbcbacbbbcaccaabacbcaabbaaacaacccaaabbbcabbbcccacacaccaacbccabccbcacbbbbbabcbabbc...