QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290105 | #5065. Beautiful String | Remakee# | WA | 153ms | 199420kb | C++14 | 976b | 2023-12-24 13:28:56 | 2023-12-24 13:28:56 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
typedef long long LL;
int n, f[N][N], g[N][N];
char s[N];
void clr() {
for (int i = 0; i <= n + 1; i++)
for (int j = 0; j <= n + 1; j++)
f[i][j] = g[i][j] = 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = n; i; i--) {
for (int j = n; j; j--) {
if (s[i] == s[j])
f[i][j] = f[i + 1][j + 1] + 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i - j >= 1 && f[i - j][i] >= j)
g[i][j] = 1;
g[i][j] += g[i][j - 1];
}
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
int u = min(f[i][j], j - i - 1);
if (u) ans += g[i][u - 1];
}
}
printf("%lld\n", ans);
clr();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
2 114514 0000000
output:
1 3
result:
ok 2 number(s): "1 3"
Test #2:
score: -100
Wrong Answer
time: 153ms
memory: 199420kb
input:
11 79380 2483905227 37902399703986576270 39991723655814713848046032694137883815354365954917 5541883522667841718787744915558298207485830622522715211018760095628594390563630840464643840093757297 56530485554219245862513973750218715585679416120445975390556326891488719311495909340757506478400624741858999...
output:
0 0 0 1 4 19 105 104 978 1932 13689
result:
wrong answer 4th numbers differ - expected: '2', found: '1'