oj.uz

Submission #117667

# Submission time Handle Problem Language Result Execution time Memory
117667 2019-06-17T05:29:51 Z 김세빈(#2878) Ljetopica (COI19_ljetopica) C++14
17 / 100
 25 ms 16128 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

char S[1010], A[1010], B[1010];
ll dp[1010][1010], C[1010][1010], T[1010];
ll n, k, ans;

ll f()
{
	ll i, j, x;

	C[n + 1][0] = 1;

	for(i=n; i>=1; i--){
		for(j=0; j<=k; j++){
			dp[i][j] = dp[i + 1][j];
			C[i][j] = C[i + 1][j];
			if((k - j & 1) ^ (S[i - 1] == 'R')) dp[i][j] = (dp[i][j] + T[n - i] * C[i + 1][j]) % mod;

			if(j){
				dp[i][j] = (dp[i][j] + dp[i + 1][j - 1]) % mod;
				C[i][j] = (C[i][j] + C[i + 1][j - 1]) % mod;
				if((k - j + 1 & 1) ^ (S[i - 1] == 'R')) dp[i][j] = (dp[i][j] + T[n - i] * C[i + 1][j - 1]) % mod;
			}
		}
	}
/*
	for(i=1; i<=n; i++){
		for(j=0; j<=k; j++){
			printf("%lld ", dp[i][j]);
		}
		printf("\n");
	}
*/
	ll s1, s2, c1, c2;

	s1 = s2 = 0; c1 = c2 = 0;
/*
	for(i=1, j=k, x=0; i<=n; i++){
		if(A[i] == '0'){
			if((k - j & 1) ^ (S[i - 1] == 'R')) j --;
			x = x * 2 % mod;
		}
		else{
			if((k - j & 1) ^ (S[i - 1] == 'L')){
				s1 = (s1 + dp[i + 1][j] + C[i + 1][j] * x % mod * T[n - i]) % mod;
				c1 = (c1 + C[i + 1][j]) % mod;
				j --;
			}
			else{
				if(j){
					s1 = (s1 + dp[i + 1][j - 1] + C[i + 1][j - 1] * x % mod * T[n - i]) % mod;
					c1 = (c1 + C[i + 1][j - 1]) % mod;
				}
			}
			x = (x * 2 + 1) % mod;
		}

		if(j < 0) break;
	}

	for(i=1, j=k, x=0; i<=n; i++){
		if(B[i] == '1'){
			if((k - j & 1) ^ (S[i - 1] == 'L')) j --;
			x = (x * 2 + 1) % mod;
		}
		else{
			if((k - j & 1) ^ (S[i - 1] == 'R')){
				s2 = (s2 + dp[i + 1][j] + C[i + 1][j] * x % mod * T[n - i]) % mod;
				c2 = (c2 + C[i + 1][j]) % mod; 
				j --;
			}
			else{
				if(j){
					s2 = (s2 + dp[i + 1][j - 1] + C[i + 1][j - 1] * x % mod * T[n - i]) % mod;
					c2 = (c2 + C[i + 1][j - 1]) % mod;
				}
			}
			x = x * 2 % mod;
		}

		if(j < 0) break;
	}

	printf("%lld %lld %lld\n", C[1][k], c1, c2);
*/

	return ((dp[1][k] - s1 - s2) + (C[1][k] - c1 - c2) * T[n]) % mod;
}

int main()
{
	ll i;

	scanf("%lld%lld", &n, &k); n --;
	scanf("%s%s%s", S, A, B);

	T[0] = 1;

	for(i=1; i<=n; i++){
		T[i] = T[i - 1] * 2 % mod;
	}

	ans = f();	

	for(i=0; i<n; i++){
		S[i] = (int)'L' + 'R' - S[i];
	}

	ans = (ans + f()) % mod;

	printf("%lld\n", (ans + mod) % mod);

	return 0;
}

Compilation message

ljetopica.cpp: In function 'll f()':
ljetopica.cpp:23:10: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    if((k - j & 1) ^ (S[i - 1] == 'R')) dp[i][j] = (dp[i][j] + T[n - i] * C[i + 1][j]) % mod;
        ~~^~~
ljetopica.cpp:28:15: warning: suggest parentheses around '+' in operand of '&' [-Wparentheses]
     if((k - j + 1 & 1) ^ (S[i - 1] == 'R')) dp[i][j] = (dp[i][j] + T[n - i] * C[i + 1][j - 1]) % mod;
         ~~~~~~^~~
ljetopica.cpp:15:11: warning: unused variable 'x' [-Wunused-variable]
  ll i, j, x;
           ^
ljetopica.cpp: In function 'int main()':
ljetopica.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &k); n --;
  ~~~~~^~~~~~~~~~~~~~~~~~~~
ljetopica.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s%s%s", S, A, B);
  ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 16128 KB Output is correct
2 Correct 17 ms 14564 KB Output is correct
3 Correct 18 ms 15480 KB Output is correct
4 Correct 25 ms 16128 KB Output is correct
5 Correct 16 ms 14208 KB Output is correct
6 Correct 25 ms 16128 KB Output is correct
7 Correct 12 ms 11904 KB Output is correct
8 Correct 18 ms 15232 KB Output is correct
9 Correct 7 ms 8576 KB Output is correct
10 Correct 17 ms 14592 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8320 KB Output isn't correct
2 Halted 0 ms 0 KB -