Submission #233662

# Submission time Handle Problem Language Result Execution time Memory
233662 2020-05-21T10:04:34 Z Vimmer Ljetopica (COI19_ljetopica) C++14
8 / 100
50 ms 29944 KB
#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];

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

ll fx(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;

    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 (dp[i][j][fl][fr][t] == 0) continue;

                    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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                }
                            }
                            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, dp[i][j][fl][fr][t]));
                                }
                            }

                            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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                    }
                                }
                                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, dp[i][j][fl][fr][t]));
                                    }
                                }
                            }
                        }
                        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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                            }
                            else
                                if (l[i + 1] != '1') dob(dp[i + 1][j][fl][fr][t], fx(2, dp[i][j][fl][fr][t]));


                            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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                }
                                else
                                    if (l[i + 1] != '1') dob(dp[i + 1][j + 1][fl][fr][1], fx(2, dp[i][j][fl][fr][t]));
                            }
                        }
                        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, dp[i][j][fl][fr][t]));
                            }
                            else
                                if (r[i + 1] != '0') dob(dp[i + 1][j][fl][fr][t], (1 + fx(2, dp[i][j][fl][fr][t])) % M);

                            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, dp[i][j][fl][fr][t]));
                                }
                                else
                                    if (r[i + 1] != '0') dob(dp[i + 1][j + 1][fl][fr][1], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                            }
                        }
                        else
                        {
                            if (s[i] == '0')  dob(dp[i + 1][j][fl][fr][t], fx(2, dp[i][j][fl][fr][t]));
                              else dob(dp[i + 1][j][fl][fr][t], (1 + fx(2, dp[i][j][fl][fr][t])) % M);

                            if (j != k)
                            {
                                if (s[i] == '0') dob(dp[i + 1][j + 1][fl][fr][1], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                  else dob(dp[i + 1][j + 1][fl][fr][1], fx(2, dp[i][j][fl][fr][t]));
                            }
                        }
                    }
                    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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                }
                            }
                            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, dp[i][j][fl][fr][t]));
                                }
                            }

                            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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                    }
                                }
                                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, dp[i][j][fl][fr][t]));
                                    }
                                }
                            }
                        }
                        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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                            }
                            else
                                if (l[i + 1] != '1') dob(dp[i + 1][j][fl][fr][t], fx(2, dp[i][j][fl][fr][t]));

                            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], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                }
                                else
                                    if (l[i + 1] != '1') dob(dp[i + 1][j + 1][fl][fr][0], fx(2, dp[i][j][fl][fr][t]));
                            }
                        }
                        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, dp[i][j][fl][fr][t]));
                            }
                            else
                                if (r[i + 1] != '0') dob(dp[i + 1][j][fl][fr][t], (1 + fx(2, dp[i][j][fl][fr][t])) % M);

                            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, dp[i][j][fl][fr][t]));
                                }
                                else
                                    if (r[i + 1] != '0') dob(dp[i + 1][j + 1][fl][fr][0], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                            }
                        }
                        else
                        {
                            if (s[i] == '1')  dob(dp[i + 1][j][fl][fr][t], fx(2, dp[i][j][fl][fr][t]));
                              else dob(dp[i + 1][j][fl][fr][t], (1 + fx(2, dp[i][j][fl][fr][t])) % M);

                            if (j != k)
                            {
                                if (s[i] == '1') dob(dp[i + 1][j + 1][fl][fr][0], (1 + fx(2, dp[i][j][fl][fr][t])) % M);
                                  else dob(dp[i + 1][j + 1][fl][fr][0], fx(2, dp[i][j][fl][fr][t]));
                            }
                        }
                    }
                }

    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;
}
# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4096 KB Output is correct
4 Correct 7 ms 3840 KB Output is correct
5 Correct 7 ms 3712 KB Output is correct
6 Correct 7 ms 3456 KB Output is correct
7 Correct 8 ms 3328 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 50 ms 29944 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 7 ms 4224 KB Output is correct
3 Correct 7 ms 4096 KB Output is correct
4 Correct 7 ms 3840 KB Output is correct
5 Correct 7 ms 3712 KB Output is correct
6 Correct 7 ms 3456 KB Output is correct
7 Correct 8 ms 3328 KB Output is correct
8 Correct 6 ms 3072 KB Output is correct
9 Incorrect 5 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -