QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511715 | #2273. Suffixes may Contain Prefixes | cocoa_chan | WA | 11ms | 12076kb | C++17 | 2.0kb | 2024-08-10 10:18:17 | 2024-08-10 10:18:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll inf=1e9;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,a[1100000],adj[2200][30],mx[2200][30],b[1100000],dp[2200][2200],pos[2200];
char c[1100000];
int main()
{
scanf("%s",c);
n=strlen(c);
scanf("%lld",&m);
for(i=1;i<=n;i++)
{
a[i]=c[i-1]-'a'+1;
}
adj[0][a[1]]=1;
mx[0][a[1]]=1;
for(i=1;i<=n;i++)
{
/*printf("%lld:",i);
for(j=0;j<=26;j++)
printf("%lld",pos[j]);
printf("\n");
*/
for(j=1;j<i;j++)
{
if(!pos[j])
continue;
//adj[i][a[i+1-j+1]]++;
/*if(mx[i][a[i+1-j+1]]==0)
mx[i][a[i+1-j+1]]=(j);*/
adj[i][a[i+1-j+1]]++;
mx[i][a[i+1-j+1]]=max(mx[i][a[i+1-j+1]],i+1-j+1);
}
if(a[i]==a[1])
{pos[i]=1;
adj[i][a[2]]++;
mx[i][a[2]]=max(mx[i][a[2]],ll(2));
}
mx[i][a[1]]=max(mx[i][a[1]],ll(1));
adj[i][a[1]]++;
for(j=1;j<=i;j++)
{
if(a[i+1]!=a[i+1-j+1])
pos[j]=0;
}
}
/* for(i=1;i<=n;i++)
{
for(j=0;j<=26;j++)
printf("(%lld,%lld) ",adj[i][j],mx[i][j]);
printf("\n");
}
*/ /*for(i=0;i<m;i++)
{
for(j=0;j<=26;j++)
{
dp[i+1][mx[i][j]]=max(dp[i+1][mx[i][j]],dp[i][j]+adj[i][j]);
}
}*/
for(i=1;i<=26;i++)
dp[0][i]=-inf;
for(i=1;i<=m;i++)
for(j=0;j<=n;j++)
dp[i][j]=-inf;
for(i=0;i<m;i++)
{
for(j=0;j<=n;j++)
{
for(k=1;k<=26;k++)
{
dp[i+1][mx[j][k]]=max(dp[i+1][mx[j][k]],dp[i][j]+adj[j][k]);
}
}
}
s=0;
/*for(i=1;i<=m;i++)
{
for(j=0;j<=26;j++)
printf("%lld ",dp[i][j]);
printf("\n");
}*/
for(j=0;j<=n;j++)
{
s=max(s,dp[m][j]);
}
printf("%lld",s);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 11ms
memory: 12076kb
input:
fsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfffsfffffsfffsfsfsfffsfffssfsfffsfsfffsfffffsfffsfffssfsfffsfsfffsffssfffsfffsfffssfsfffsfsfsfsfffsfffssfsfffsfsf...
output:
1189
result:
wrong answer 1st lines differ - expected: '852', found: '1189'