oj.uz

답안 #97459

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
97459 2019-02-16T10:41:12 Z Kastanda 원형 문자열 (IZhO13_rowords) C++11
100 / 100
 372 ms 86648 KB 
// I do it for the glory
#include<bits/stdc++.h>
using namespace std;
const int N = 2009, NN = N * 2;
int n, m, dp[NN][N], P[NN][N], F[N][NN];
char A[NN], B[N];
inline void Sub(int j, int i) // Subtract one from i-th first element of column j.
{
    for (i = NN - i - 1; i < NN; i += i & -i)
        F[j][i] ++;
}
inline int Get(int i, int j) // value of dp[i][j].
{
    int ret = dp[i][j];
    for (i = NN - i - 1; i; i -= i & -i)
        ret -= F[j][i];
    return (ret);
}
inline int RLCS()
{
    int Mx = 0;
    memset(F, 0, sizeof(F));
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            dp[i][j] = max({dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + (A[i] == B[j])});
            if (dp[i][j] == dp[i][j - 1])
                P[i][j] = 2;
            else if (A[i] == B[j] && dp[i][j] == dp[i - 1][j - 1] + 1)
                P[i][j] = 1;
            else
                P[i][j] = 0;
        }
    Mx = dp[n][m];

    for (int i = n + 1; i <= n + n; i++)
    {
        /* **** Deleting the first row **** */

        int last = i - n, nw = 0;
        for (int j = 1; j <= m; j++)
        {
            if (last != i && P[last][j] != 2)
            {
                P[last][j] = 2;
                last ++;
                while (last < i && P[last][j] == 0)
                    P[last][j] = 2, last ++;
            }
            Sub(j, last - 1);
        }

        /* **** Adding the last row **** */

        for (int j = 1; j <= m; j++)
        {
            int _0 = Get(i - 1, j);
            int _1 = Get(i - 1, j - 1);
            int _2 = Get(i, j - 1);
            dp[i][j] = max({_0, _1 + (A[i] == B[j]), _2});
            if (dp[i][j] == _2)
                P[i][j] = 2;
            else if (A[i] == B[j] && dp[i][j] == _1 + 1)
                P[i][j] = 1;
            else
                P[i][j] = 0;
        }

        Mx = max(Mx, dp[i][m]);
    }
    return (Mx);
}
int main()
{
    scanf("%s%s", A + 1, B + 1);
    n = strlen(A + 1);
    m = strlen(B + 1);
    memcpy(A + n + 1, A + 1, n);
    int Mx = RLCS();
    reverse(B + 1, B + m + 1);
    return !printf("%d\n", max(Mx, RLCS()));
}

Compilation message

rowords.cpp: In function 'int RLCS()':
rowords.cpp:41:27: warning: unused variable 'nw' [-Wunused-variable]
         int last = i - n, nw = 0;
                           ^~
rowords.cpp: In function 'int main()':
rowords.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s%s", A + 1, B + 1);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 63608 KB Output is correct
2 Correct 67 ms 63608 KB Output is correct
3 Correct 68 ms 63608 KB Output is correct
4 Correct 72 ms 63980 KB Output is correct
5 Correct 68 ms 63864 KB Output is correct
6 Correct 86 ms 72440 KB Output is correct
7 Correct 239 ms 79224 KB Output is correct
8 Correct 295 ms 79252 KB Output is correct
9 Correct 296 ms 79304 KB Output is correct
10 Correct 281 ms 79284 KB Output is correct
11 Correct 303 ms 80888 KB Output is correct
12 Correct 353 ms 82388 KB Output is correct
13 Correct 368 ms 82448 KB Output is correct
14 Correct 330 ms 81528 KB Output is correct
15 Correct 372 ms 82936 KB Output is correct
16 Correct 355 ms 80456 KB Output is correct
17 Correct 238 ms 81656 KB Output is correct
18 Correct 348 ms 85660 KB Output is correct
19 Correct 290 ms 79224 KB Output is correct
20 Correct 346 ms 83412 KB Output is correct
21 Correct 112 ms 79224 KB Output is correct
22 Correct 171 ms 81500 KB Output is correct
23 Correct 187 ms 83012 KB Output is correct
24 Correct 186 ms 83960 KB Output is correct
25 Correct 256 ms 86648 KB Output is correct