Submission #13638

#	Time	Username	Problem	Language	Result	Execution time	Memory
13638		dohyun0324	Round words (IZhO13_rowords)	C++98	48 / 100	2072 ms	46712 KiB

rowords

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int dap,maxi,n,m,p,d[4010][4010],lena,lenb,par[4010][4010];
char a[4010],b[4010];
void lcs(int x)
{
    int i=n+x,j=m,cnt=0;
    while(1)
    {
        if(i==x+1 && j==1) break;
        if(par[i][j]==1) i--;
        else if(par[i][j]==2) j--;
        else if(par[i][j]==3) i--, j--;
        cnt++;
    }
    if(dap<n+m-1-cnt) dap=n+m-1-cnt;
}
void pro()
{
    int i,j,x,y;
    //make edge
    for(i=1;i<=n*2;i++)
    {
        for(j=1;j<=m;j++)
        {
            maxi=-2147483647;
            if(maxi<d[i][j-1]) maxi=d[i][j-1], p=2;
            if(maxi<d[i-1][j-1]+(a[i]==b[j])) maxi=d[i-1][j-1]+1, p=3;
            if(maxi<d[i-1][j]) maxi=d[i-1][j], p=1;
            par[i][j]=p; d[i][j]=maxi;
        }
    }
    for(i=1;i<=m;i++) par[1][i]=2;
    for(i=1;i<=n*2;i++) par[i][1]=1;
    if(dap<d[n][m]) dap=d[n][m];
    for(i=1;i<n;i++)
    {
        //remove first row
        for(j=1;j<=m;j++)
        {
            if(par[i+1][j]==3) break;
        }
        x=i+1; y=j;
        for(j=y;j<=m;j++) par[i+1][j]=2;
        //merge two tree
        while(x<2*n && y<=m)
        {
            if(par[x+1][y]==1)
            {
                par[x+1][y]=2;
                x++;
            }
            else if(par[x+1][y+1]==3)
            {
                par[x+1][y+1]=2;
                x++; y++;
            }
            else y++;
        }
        lcs(i);
    }
}
int main()
{
    int i;
    scanf("%s",a); n=strlen(a);
    scanf("%s",b); m=strlen(b);
    for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
    for(i=m;i>=1;i--) b[i]=b[i-1]; b[0]=0;
    for(i=n+1;i<=n*2;i++) a[i]=a[i-n];
    pro();
    reverse(a+1,a+n*2+1);
    pro();
    printf("%d",dap);
    return 0;
}

Compilation message (stderr)

rowords.cpp: In function 'int main()':
rowords.cpp:70:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
     ^~~
rowords.cpp:70:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
                                    ^
rowords.cpp:71:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for(i=m;i>=1;i--) b[i]=b[i-1]; b[0]=0;
     ^~~
rowords.cpp:71:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
     for(i=m;i>=1;i--) b[i]=b[i-1]; b[0]=0;
                                    ^
rowords.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",a); n=strlen(a);
     ~~~~~^~~~~~~~
rowords.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",b); m=strlen(b);
     ~~~~~^~~~~~~~

• Subtask 1: 48 / 100