oj.uz

Submission #97457

# Submission time Handle Problem Language Result Execution time Memory
97457 2019-02-16T10:26:24 Z Kastanda Round words (IZhO13_rowords) C++11
72 / 100
 388 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 + 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

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

# Verdict Execution time Memory Grader output
1 Correct 66 ms 63608 KB Output is correct
2 Incorrect 66 ms 63608 KB Output isn't correct
3 Correct 66 ms 63736 KB Output is correct
4 Correct 67 ms 63836 KB Output is correct
5 Incorrect 66 ms 63836 KB Output isn't correct
6 Correct 87 ms 72268 KB Output is correct
7 Correct 255 ms 79340 KB Output is correct
8 Correct 379 ms 79352 KB Output is correct
9 Correct 306 ms 79348 KB Output is correct
10 Correct 289 ms 79208 KB Output is correct
11 Correct 303 ms 80924 KB Output is correct
12 Correct 342 ms 82424 KB Output is correct
13 Correct 388 ms 82400 KB Output is correct
14 Incorrect 335 ms 81488 KB Output isn't correct
15 Correct 386 ms 83064 KB Output is correct
16 Incorrect 338 ms 80636 KB Output isn't correct
17 Correct 243 ms 81656 KB Output is correct
18 Incorrect 353 ms 85740 KB Output isn't correct
19 Incorrect 281 ms 79324 KB Output isn't correct
20 Correct 342 ms 83372 KB Output is correct
21 Correct 114 ms 79200 KB Output is correct
22 Correct 151 ms 81400 KB Output is correct
23 Correct 190 ms 82936 KB Output is correct
24 Incorrect 219 ms 83984 KB Output isn't correct
25 Correct 254 ms 86648 KB Output is correct