Submission #233681

#	Time	Username	Problem	Language	Result	Execution time	Memory
233681		Vimmer	Ljetopica (COI19_ljetopica)	C++14	100 / 100	103 ms	77816 KiB

ljetopica

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")

#define sz(x) ll(x.size())
#define base 1000000
#define M ll(1e9+7)
#define N 100005
#define F first
#define S second
#define pb push_back
#define in insert
#define eb emplace_back
#define ed "\n"

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef short int si;

//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


ll dp[1005][1005][2][2][2], kol[1005][1005][2][2][2];

bool mk[1005][1005][2][2][2];

void dob(ll &x, ll y) {x += y; x %= M;}

ll fx(ll x, ll y) {return (x * y) % M;}

ll sm(ll x, ll y) {return (x + y) % M;}

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, k;

    cin >> n >> k;

    string s;

    cin >> s;

    for (int i = 0; i < sz(s); i++) if (s[i] == 'L') s[i] = '0'; else s[i] = '1';

    string l, r;

    cin >> l >> r;

    mk[0][0][1][1][0] = mk[0][0][1][1][1] = 1;

    kol[0][0][1][1][0] = kol[0][0][1][1][1] = dp[0][0][1][1][0] = dp[0][0][1][1][1] = 1;

    n--;

    for (int i = 0; i < n; i++)
        for (int j = 0; j <= k; j++)
          for (int fl = 0; fl < 2; fl++)
            for (int fr = 0; fr < 2; fr++)
              for (int t = 0; t < 2; t++)
                {
                    if (!mk[i][j][fl][fr][t]) continue;

                    ll val = dp[i][j][fl][fr][t], koler = kol[i][j][fl][fr][t];

                    if (t == 0)
                    {
                        if (fl && fr)
                        {
                            if (s[i] == '1')
                            {
                                if (r[i + 1] != '0')
                                {
                                    int nfl = fl;

                                    if (l[i + 1] == '0') nfl = 0;

                                    dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));

                                    mk[i + 1][j][nfl][fr][t] = 1;

                                    dob(kol[i + 1][j][nfl][fr][t], koler);
                                }
                            }
                            else
                            {
                                if (l[i + 1] != '1')
                                {
                                    int nfr = fr;

                                    if (r[i + 1] == '1') nfr = 0;

                                    dob(dp[i + 1][j][fl][nfr][t], fx(2, val));

                                    mk[i + 1][j][fl][nfr][t] = 1;

                                    dob(kol[i + 1][j][fl][nfr][t], koler);
                                }
                            }

                            if (j != k)
                            {
                                if (s[i] == '0')
                                {
                                    if (r[i + 1] != '0')
                                    {
                                        int nfl = fl;

                                        if (l[i + 1] == '0') nfl = 0;

                                        dob(dp[i + 1][j + 1][nfl][fr][1], sm(koler, fx(2, val)));

                                        mk[i + 1][j + 1][nfl][fr][1] = 1;

                                        dob(kol[i + 1][j + 1][nfl][fr][1], koler);
                                    }
                                }
                                else
                                {
                                    if (l[i + 1] != '1')
                                    {
                                        int nfr = fr;

                                        if (r[i + 1] == '1') nfr = 0;

                                        dob(dp[i + 1][j + 1][fl][nfr][1], fx(2, val));

                                        mk[i + 1][j + 1][fl][nfr][1] = 1;

                                        dob(kol[i + 1][j + 1][fl][nfr][1], koler);
                                    }
                                }
                            }
                        }
                        else if (fl)
                        {
                            if (s[i] == '1')
                            {
                                int nfl = fl;

                                if (l[i + 1] == '0') nfl = 0;

                                dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));

                                mk[i + 1][j][nfl][fr][t] = 1;

                                dob(kol[i + 1][j][nfl][fr][t], koler);
                            }
                            else
                                if (l[i + 1] != '1')
                                {
                                    dob(dp[i + 1][j][fl][fr][t], fx(2, val));

                                    mk[i + 1][j][fl][fr][t] = 1;

                                    dob(kol[i + 1][j][fl][fr][t], koler);
                                }

                            if (j != k)
                            {
                                if (s[i] == '0')
                                {
                                    int nfl = fl;

                                    if (l[i + 1] == '0') nfl = 0;

                                    dob(dp[i + 1][j + 1][nfl][fr][1], sm(koler, fx(2, val)));

                                    mk[i + 1][j + 1][nfl][fr][1] = 1;

                                    dob(kol[i + 1][j + 1][nfl][fr][1], koler);
                                }
                                else
                                    if (l[i + 1] != '1')
                                    {
                                        dob(dp[i + 1][j + 1][fl][fr][1], fx(2, val));

                                        mk[i + 1][j + 1][fl][fr][1] = 1;

                                        dob(kol[i + 1][j + 1][fl][fr][1], koler);
                                    }
                            }
                        }
                        else if (fr)
                        {
                            if (s[i] == '0')
                            {
                                int nfr = fr;

                                if (r[i + 1] == '1') nfr = 0;

                                dob(dp[i + 1][j][fl][nfr][t], fx(2, val));

                                mk[i + 1][j][fl][nfr][t] = 1;

                                dob(kol[i + 1][j][fl][nfr][t], koler);
                            }
                            else
                                if (r[i + 1] != '0')
                                {
                                    dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));

                                    mk[i + 1][j][fl][fr][t] = 1;

                                    dob(kol[i + 1][j][fl][fr][t], koler);
                                }

                            if (j != k)
                            {
                                if (s[i] == '1')
                                {
                                    int nfr = fr;

                                    if (r[i + 1] == '1') nfr = 0;

                                    dob(dp[i + 1][j + 1][fl][nfr][1], fx(2, val));

                                    mk[i + 1][j + 1][fl][nfr][1] = 1;

                                    dob(kol[i + 1][j + 1][fl][nfr][1], koler);
                                }
                                else
                                    if (r[i + 1] != '0')
                                    {
                                        dob(dp[i + 1][j + 1][fl][fr][1], sm(koler, fx(2, val)));

                                        mk[i + 1][j + 1][fl][fr][1] = 1;

                                        dob(kol[i + 1][j + 1][fl][fr][1], koler);
                                    }
                            }
                        }
                        else
                        {
                            if (s[i] == '0')
                            {
                                dob(dp[i + 1][j][fl][fr][t], fx(2, val));

                                mk[i + 1][j][fl][fr][t] = 1;

                                dob(kol[i + 1][j][fl][fr][t], koler);
                            }
                            else
                            {
                                dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));

                                mk[i + 1][j][fl][fr][t] = 1;

                                dob(kol[i + 1][j][fl][fr][t], koler);
                            }
                            if (j != k)
                            {
                                if (s[i] == '0')
                                {
                                    dob(dp[i + 1][j + 1][fl][fr][1], sm(koler, fx(2, val)));

                                    mk[i + 1][j + 1][fl][fr][1] = 1;

                                    dob(kol[i + 1][j + 1][fl][fr][1], koler);
                                }
                                else
                                {
                                    dob(dp[i + 1][j + 1][fl][fr][1], fx(2, val));

                                    mk[i + 1][j + 1][fl][fr][1] = 1;

                                    dob(kol[i + 1][j + 1][fl][fr][1], koler);
                                }
                            }
                        }
                    }
                    else
                    {
                        if (fl && fr)
                        {
                            if (s[i] == '0')
                            {
                                if (r[i + 1] != '0')
                                {
                                    int nfl = fl;

                                    if (l[i + 1] == '0') nfl = 0;

                                    dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));

                                    mk[i + 1][j][nfl][fr][t] = 1;

                                    dob(kol[i + 1][j][nfl][fr][t], koler);
                                }
                            }
                            else
                            {
                                if (l[i + 1] != '1')
                                {
                                    int nfr = fr;

                                    if (r[i + 1] == '1') nfr = 0;

                                    dob(dp[i + 1][j][fl][nfr][t], fx(2, val));

                                    mk[i + 1][j][fl][nfr][t] = 1;

                                    dob(kol[i + 1][j][fl][nfr][t], koler);
                                }
                            }

                            if (j != k)
                            {
                                if (s[i] == '1')
                                {
                                    if (r[i + 1] != '0')
                                    {
                                        int nfl = fl;

                                        if (l[i + 1] == '0') nfl = 0;

                                        dob(dp[i + 1][j + 1][nfl][fr][0], sm(koler, fx(2, val)));

                                        mk[i + 1][j + 1][nfl][fr][0] = 1;

                                        dob(kol[i + 1][j + 1][nfl][fr][0], koler);
                                    }
                                }
                                else
                                {
                                    if (l[i + 1] != '1')
                                    {
                                        int nfr = fr;

                                        if (r[i + 1] == '1') nfr = 0;

                                        dob(dp[i + 1][j + 1][fl][nfr][0], fx(2, val));

                                        mk[i + 1][j + 1][fl][nfr][0] = 1;

                                        dob(kol[i + 1][j + 1][fl][nfr][0], koler);
                                    }
                                }
                            }
                        }
                        else if (fl)
                        {
                            if (s[i] == '0')
                            {
                                int nfl = fl;

                                if (l[i + 1] == '0') nfl = 0;

                                dob(dp[i + 1][j][nfl][fr][t], sm(koler, fx(2, val)));

                                mk[i + 1][j][nfl][fr][t] = 1;

                                dob(kol[i + 1][j][nfl][fr][t], koler);
                            }
                            else
                                if (l[i + 1] != '1')
                                {
                                    dob(dp[i + 1][j][fl][fr][t], fx(2, val));

                                    mk[i + 1][j][fl][fr][t] = 1;

                                    dob(kol[i + 1][j][fl][fr][t], koler);
                                }

                            if (j != k)
                            {
                                if (s[i] == '1')
                                {
                                    int nfl = fl;

                                    if (l[i + 1] == '0') nfl = 0;

                                    dob(dp[i + 1][j + 1][nfl][fr][0], sm(koler, fx(2, val)));

                                    mk[i + 1][j + 1][nfl][fr][0] = 1;

                                    dob(kol[i + 1][j + 1][nfl][fr][0], koler);
                                }
                                else
                                    if (l[i + 1] != '1')
                                    {
                                        dob(dp[i + 1][j + 1][fl][fr][0], fx(2, val));

                                        mk[i + 1][j + 1][fl][fr][0] = 1;

                                        dob(kol[i + 1][j + 1][fl][fr][0], koler);
                                    }
                            }
                        }
                        else if (fr)
                        {
                            if (s[i] == '1')
                            {
                                int nfr = fr;

                                if (r[i + 1] == '1') nfr = 0;

                                dob(dp[i + 1][j][fl][nfr][t], fx(2, val));

                                mk[i + 1][j][fl][nfr][t] = 1;

                                dob(kol[i + 1][j][fl][nfr][t], koler);
                            }
                            else
                                if (r[i + 1] != '0')
                                {
                                    dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));

                                    mk[i + 1][j][fl][fr][t] = 1;

                                    dob(kol[i + 1][j][fl][fr][t], koler);
                                }

                            if (j != k)
                            {
                                if (s[i] == '0')
                                {
                                    int nfr = fr;

                                    if (r[i + 1] == '1') nfr = 0;

                                    dob(dp[i + 1][j + 1][fl][nfr][0], fx(2, val));

                                    mk[i + 1][j + 1][fl][nfr][0] = 1;

                                    dob(kol[i + 1][j + 1][fl][nfr][0], koler);
                                }
                                else
                                    if (r[i + 1] != '0')
                                    {
                                        dob(dp[i + 1][j + 1][fl][fr][0], sm(koler, fx(2, val)));

                                        mk[i + 1][j + 1][fl][fr][0] = 1;

                                        dob(kol[i + 1][j + 1][fl][fr][0], koler);
                                    }
                            }
                        }
                        else
                        {
                            if (s[i] == '1')
                            {
                                dob(dp[i + 1][j][fl][fr][t], fx(2, val));

                                mk[i + 1][j][fl][fr][t] = 1;

                                dob(kol[i + 1][j][fl][fr][t], koler);
                            }
                            else
                            {
                                dob(dp[i + 1][j][fl][fr][t], sm(koler, fx(2, val)));

                                mk[i + 1][j][fl][fr][t] = 1;

                                dob(kol[i + 1][j][fl][fr][t], koler);
                            }

                            if (j != k)
                            {
                                if (s[i] == '1')
                                {
                                    dob(dp[i + 1][j + 1][fl][fr][0], sm(koler, fx(2, val)));

                                    mk[i + 1][j + 1][fl][fr][0] = 1;

                                    dob(kol[i + 1][j + 1][fl][fr][0], koler);
                                }
                                else
                                {
                                    dob(dp[i + 1][j + 1][fl][fr][0], fx(2, val));

                                    mk[i + 1][j + 1][fl][fr][0] = 1;

                                    dob(kol[i + 1][j + 1][fl][fr][0], koler);
                                }
                            }
                        }
                    }
                }

    ll ans_nakanecto = 0;

    dob(ans_nakanecto, dp[n][k][0][0][0]);

    dob(ans_nakanecto, dp[n][k][0][0][1]);

    dob(ans_nakanecto, dp[n][k][0][1][0]);

    dob(ans_nakanecto, dp[n][k][0][1][1]);

    dob(ans_nakanecto, dp[n][k][1][0][0]);

    dob(ans_nakanecto, dp[n][k][1][0][1]);

    dob(ans_nakanecto, dp[n][k][1][1][0]);

    dob(ans_nakanecto, dp[n][k][1][1][1]);

    cout << ans_nakanecto << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61