QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511715#2273. Suffixes may Contain Prefixescocoa_chanWA 11ms12076kbC++172.0kb2024-08-10 10:18:172024-08-10 10:18:20

Judging History

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

  • [2024-08-10 10:18:20]
  • 评测
  • 测评结果:WA
  • 用时:11ms
  • 内存:12076kb
  • [2024-08-10 10:18:17]
  • 提交

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'