oj.uz

답안 #134534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134534 2019-07-23T02:46:23 Z luciocf Ljetopica (COI19_ljetopica) C++14
0 / 100
 70 ms 34076 KB 
#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 1e3+10;
const int mod = 1e9+7;

typedef long long ll;
typedef pair<ll, ll> pii;

int n, k;
int pot[maxn];

char pos[maxn], A[maxn];

bool mark[maxn][maxn][2][2];

pii dp[maxn][maxn][2][2];

void change(void)
{
	int last = 0;
	for (int i = n-1; i >= 0; i--)
	{
		if (A[i] == '1')
		{
			last = i;
			break;
		}
	}

	A[last] = '0';
	for (int i = last+1; i < n; i++)
		A[i] = '1';
}

pii solve(int depth, int r, int q, int flag)
{
	if (mark[depth][r][q][flag]) return dp[depth][r][q][flag];
	if (depth == n && r != 0) return {0, 0};
	if (depth == n) return {0, 1};

	mark[depth][r][q][flag] = true;

	if (!r) 
	{
		char c = pos[depth];

		if (!q && c == 'L') c = 'R';
		else if (!q && c == 'R') c = 'L';

		pii ans = solve(depth+1, 0, q, (flag || (A[depth]=='1')));

		if (c == 'L') return dp[depth][r][q][flag] = ans;

		if (A[depth] == '1' || flag) return dp[depth][r][q][flag] = {(1ll*pot[n-depth-1]*ans.ss)%mod, ans.ss};
		return {0, 0};
	}

	char c = pos[depth];
	if (!q && c == 'L') c = 'R';
	else if (!q && c == 'R') c = 'L';

	if (c == 'L')
	{
		pii ans1 = solve(depth+1, r, q, (flag || (A[depth]=='1')));
		pii ans2 = solve(depth+1, r-1, !q, (flag || (A[depth]=='1')));

		return dp[depth][r][q][flag] = {(ans1.ff+ans2.ff)%mod, (ans1.ss+ans2.ss)%mod};
	}
	else
	{
		pii ans = {0, 0};

		if (A[depth] == '1' || flag)
		{
			pii sub1 = solve(depth+1, r, q, flag);
			pii sub2 = solve(depth+1, r-1, !q, flag);

			ans = {(sub1.ff+sub2.ff)%mod, (sub1.ss+sub2.ss)%mod};

			ans.ff = (ans.ff + ((1ll*pot[n-depth-1]*ans.ss)%mod))%mod;
		}

		return dp[depth][r][q][flag] = ans;
	}
}

int main(void)
{
	scanf("%d %d", &n, &k);

	pot[0] = 1;
	for (int i = 1; i <= n; i++)
		pot[i] = (2*pot[i-1])%mod;

	for (int i = 1; i < n; i++)
		scanf(" %c", &pos[i]);

	for (int i = 0; i < n; i++)
		scanf(" %c", &A[i]);

	change();

	int ans1 = 0;

	if (A[0] != '0')
	{
		pii sub1 = solve(1, k, 1, 0);
		memset(mark, 0, sizeof mark);
		pii sub2 = solve(1, k, 0, 0);

		ans1 = ((sub1.ff + sub2.ff)%mod + (1ll*pot[n-1]*sub1.ss + 1ll*pot[n-1]*sub2.ss)%mod)%mod;
	}

	memset(mark, 0, sizeof mark);

	for (int i = 0; i < n; i++)
		scanf(" %c", &A[i]);

	pii sub1 = solve(1, k, 1, 0);
	memset(mark, 0, sizeof mark);
	pii sub2 = solve(1, k, 0, 0);

	int ans2 = ((sub1.ff + sub2.ff)%mod + (1ll*pot[n-1]*sub1.ss + 1ll*pot[n-1]*sub2.ss)%mod)%mod;

	printf("%d\n", ans2-ans1);
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
ljetopica.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &pos[i]);
   ~~~~~^~~~~~~~~~~~~~~~
ljetopica.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &A[i]);
   ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &A[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 8568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 4472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 34076 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 8568 KB Output isn't correct
2 Halted 0 ms 0 KB -