QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#870610#9514. 研心NineSuns20 4861ms31756kbC++14807b2025-01-25 17:02:362025-01-25 17:02:42

Judging History

你现在查看的是最新测评结果

  • [2025-01-25 17:02:42]
  • 评测
  • 测评结果:20
  • 用时:4861ms
  • 内存:31756kb
  • [2025-01-25 17:02:36]
  • 提交

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; 
}

Details

Tip: Click on the bar to expand more detailed information

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...

output:


result: