oj.uz

답안 #13644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13644 2015-02-26T15:52:03 Z dohyun0324 원형 문자열 (IZhO13_rowords) C++
100 / 100
 170 ms 46588 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+1,j=m,cnt=0;
    while(1)
    {
        if(i==x+1 && j==0) 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-cnt) dap=n+m-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[0][i]=2;
    for(i=1;i<=n*2;i++) par[i][0]=1;
    if(dap<d[n][m]) dap=d[n][m];
    for(i=0;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+1); n=strlen(a+1);
    scanf("%s",b+1); m=strlen(b+1);
    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:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",a+1); n=strlen(a+1);
     ~~~~~^~~~~~~~~~
rowords.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",b+1); m=strlen(b+1);
     ~~~~~^~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 3 ms 1016 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 30 ms 17972 KB Output is correct
7 Correct 48 ms 31992 KB Output is correct
8 Correct 109 ms 32104 KB Output is correct
9 Correct 118 ms 32120 KB Output is correct
10 Correct 104 ms 32120 KB Output is correct
11 Correct 118 ms 35320 KB Output is correct
12 Correct 77 ms 39800 KB Output is correct
13 Correct 154 ms 39772 KB Output is correct
14 Correct 137 ms 36560 KB Output is correct
15 Correct 140 ms 41592 KB Output is correct
16 Correct 131 ms 34908 KB Output is correct
17 Correct 118 ms 36600 KB Output is correct
18 Correct 167 ms 44968 KB Output is correct
19 Correct 106 ms 31992 KB Output is correct
20 Correct 157 ms 40148 KB Output is correct
21 Correct 74 ms 31736 KB Output is correct
22 Correct 103 ms 36400 KB Output is correct
23 Correct 121 ms 39160 KB Output is correct
24 Correct 135 ms 41388 KB Output is correct
25 Correct 170 ms 46588 KB Output is correct