oj.uz

Submission #13638

# Submission time Handle Problem Language Result Execution time Memory
13638 2015-02-26T15:29:35 Z dohyun0324 Round words (IZhO13_rowords) C++
48 / 100
 2000 ms 46712 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Execution timed out 2041 ms 632 KB Time limit exceeded
4 Incorrect 3 ms 1016 KB Output isn't correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 30 ms 18040 KB Output is correct
7 Incorrect 49 ms 31992 KB Output isn't correct
8 Incorrect 113 ms 32120 KB Output isn't correct
9 Incorrect 118 ms 32120 KB Output isn't correct
10 Execution timed out 2072 ms 31992 KB Time limit exceeded
11 Execution timed out 2051 ms 35192 KB Time limit exceeded
12 Correct 84 ms 39800 KB Output is correct
13 Correct 157 ms 39856 KB Output is correct
14 Execution timed out 2057 ms 36804 KB Time limit exceeded
15 Execution timed out 2064 ms 41592 KB Time limit exceeded
16 Correct 131 ms 34936 KB Output is correct
17 Incorrect 115 ms 36684 KB Output isn't correct
18 Correct 159 ms 44920 KB Output is correct
19 Correct 94 ms 32120 KB Output is correct
20 Incorrect 157 ms 40084 KB Output isn't correct
21 Incorrect 72 ms 31736 KB Output isn't correct
22 Correct 101 ms 36344 KB Output is correct
23 Correct 119 ms 39248 KB Output is correct
24 Correct 130 ms 41476 KB Output is correct
25 Incorrect 167 ms 46712 KB Output isn't correct