oj.uz

Submission #13637

# Submission time Handle Problem Language Result Execution time Memory
13637 2015-02-26T15:21:10 Z dohyun0324 Round words (IZhO13_rowords) C++
12 / 100
 2000 ms 46584 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;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
12.0 / 100.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2045 ms 376 KB Time limit exceeded
2 Correct 2 ms 504 KB Output is correct
3 Execution timed out 2060 ms 632 KB Time limit exceeded
4 Execution timed out 2033 ms 1144 KB Time limit exceeded
5 Correct 3 ms 1016 KB Output is correct
6 Execution timed out 2025 ms 18040 KB Time limit exceeded
7 Execution timed out 2063 ms 31992 KB Time limit exceeded
8 Execution timed out 2061 ms 32120 KB Time limit exceeded
9 Execution timed out 2053 ms 32120 KB Time limit exceeded
10 Execution timed out 2066 ms 31992 KB Time limit exceeded
11 Execution timed out 2033 ms 35192 KB Time limit exceeded
12 Execution timed out 2073 ms 39672 KB Time limit exceeded
13 Execution timed out 2028 ms 39672 KB Time limit exceeded
14 Execution timed out 2025 ms 36600 KB Time limit exceeded
15 Execution timed out 2023 ms 41720 KB Time limit exceeded
16 Execution timed out 2029 ms 34936 KB Time limit exceeded
17 Incorrect 118 ms 36648 KB Output isn't correct
18 Execution timed out 2054 ms 44920 KB Time limit exceeded
19 Execution timed out 2040 ms 31992 KB Time limit exceeded
20 Execution timed out 2058 ms 40056 KB Time limit exceeded
21 Execution timed out 2055 ms 31736 KB Time limit exceeded
22 Execution timed out 2059 ms 36344 KB Time limit exceeded
23 Execution timed out 2058 ms 39160 KB Time limit exceeded
24 Correct 130 ms 41468 KB Output is correct
25 Execution timed out 2058 ms 46584 KB Time limit exceeded