Submission #97457

#	Time	Username	Problem	Language	Result	Execution time	Memory
97457		Kastanda	Round words (IZhO13_rowords)	C++11	72 / 100	388 ms	86648 KiB

rowords

// 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 + 1, 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 (stderr)

rowords.cpp: In function 'int RLCS()':
rowords.cpp:41:31: warning: unused variable 'nw' [-Wunused-variable]
         int last = i - n + 1, 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: 72 / 100