| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 233663 | 2020-05-21T10:07:45 Z | Vimmer | Ljetopica (COI19_ljetopica) | C++14 | 52 ms | 30048 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;
}
| # | 결과 | 실행 시간 | 메모리 | 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 | 8 ms | 3584 KB | Output is correct |
| 6 | Correct | 6 ms | 3456 KB | Output is correct |
| 7 | Correct | 6 ms | 3200 KB | Output is correct |
| 8 | Correct | 6 ms | 3072 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 5 ms | 384 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 52 ms | 30048 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | 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 | 8 ms | 3584 KB | Output is correct |
| 6 | Correct | 6 ms | 3456 KB | Output is correct |
| 7 | Correct | 6 ms | 3200 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 | - |