oj.uz

Submission #117811

# Submission time Handle Problem Language Result Execution time Memory
117811 2019-06-17T08:09:49 Z 윤지학(#2883) Ljetopica (COI19_ljetopica) C++14
25 / 100
 33 ms 31736 KB 
#include<stdio.h>
#include<stdlib.h>
 
#define MAXN 1005
 
const int MOD=1e9 + 7;
 
char ans[MAXN];
char A[MAXN], B[MAXN];
int two[MAXN];
long long dp[MAXN][MAXN][2][2];
bool cA[MAXN], cB[MAXN];
 
void add(long long* a, long long b) {
	*a = (*a + b) % MOD;
}
 
int main() {
	int N, K;
	long long res;
 
	scanf("%d%d", &N, &K);
	scanf("%s\n%s\n%s", ans, A, B);
 
	if (A[N - 1] == 0) {
		A[0] = '1';
		for (int i = 1; i < N; i++) A[i] = '0';
	}
	if (B[N] != 0) for (int i = 0; i < N; i++) B[i] = '1';
	//printf("%s*%s*%s", A, B, ans);
 
	for (int i = 0; i < N - 1; i++) {
		cA[i] = ((ans[i] == 'L' && A[i+1] == '0') || (ans[i] == 'R' && A[i+1] == '1'));
		cB[i] = ((ans[i] == 'L' && B[i+1] == '0') || (ans[i] == 'R' && B[i+1] == '1'));
		//printf("[%d %d]\n", cA[i]?1:0, cB[i]?1:0);
	}
 
	two[0] = 1;
	for (int i = 1; i < N; i++) two[i] = two[i - 1] * 2 % MOD;
 
	dp[N - 1][0][0][0] = dp[N-1][0][1][0]=1ll;
	//printf("%lld\n", dp[2][0][1][0]);
	//for (int i = 0; i < N; i++)
		//for (int j = 0; j <= K; j++) printf("i=%d, j=%d: (%lld %lld), (%lld %lld)\n", i, j, dp[i][j][0][0], dp[i][j][0][1], dp[i][j][1][0], dp[i][j][1][1]);
	for (int i = N - 2; i >= 0; i--) for(int j=0; j<=K; j++){
		dp[i][j][0][0] = dp[i + 1][j][0][0];
		dp[i][j][1][0] = dp[i + 1][j][1][0];
		if (j > 0) {
			add(&dp[i][j][0][0], dp[i + 1][j - 1][1][0]);
			add(&dp[i][j][1][0], dp[i + 1][j - 1][0][0]);
		}
		dp[i][j][0][1] = dp[i + 1][j][0][1];
		dp[i][j][1][1] = dp[i + 1][j][1][1];
		if (ans[i] == 'L') add(&dp[i][j][1][1], two[N - i - 2] * dp[i + 1][j][1][0]);
		else add(&dp[i][j][0][1], two[N - i - 2] * dp[i + 1][j][0][0]);
		if (j > 0) {
			add(&dp[i][j][0][1], dp[i + 1][j - 1][1][1]);
			add(&dp[i][j][1][1], dp[i + 1][j - 1][0][1]);
			if (ans[i] == 'L') add(&dp[i][j][0][1], two[N - i - 2] * dp[i + 1][j - 1][1][0]);
			else add(&dp[i][j][1][1], two[N - i - 2] * dp[i + 1][j - 1][0][0]);
		}
	}
 
	//for (int i = 0; i < N; i++)
		//for (int j = 0; j <= K; j++) printf("i=%d, j=%d: (%lld %lld), (%lld %lld)\n", i, j, dp[i][j][0][0], dp[i][j][0][1], dp[i][j][1][0], dp[i][j][1][1]);
 
	res = (dp[0][K][0][1] + dp[0][K][1][1] + two[N - 1] * (dp[0][K][0][0] + dp[0][K][1][0])) % MOD;
	//printf("%lld\n", res);
	long long sA=two[N-1], sB=two[N-1];
	int KA = K, KB=K;
	for (int i = 0; i < N - 1; i++) {
		if (A[i + 1] == '1') {
			//printf("@");
			if (i>0&&cA[i - 1] == cA[i]) KA--;
			//printf("(%d %lld)", KA, sA);
			if (KA >= 0) res = (res - dp[i + 1][KA][cA[i] ? 1 : 0][1] - sA * dp[i + 1][KA][cA[i] ? 1 : 0][0]) % MOD;
			if (KA > 0) res = (res - dp[i + 1][KA-1][cA[i] ? 1 : 0][1] - sA * dp[i + 1][KA-1][cA[i] ? 1 : 0][0]) % MOD;
			if (i>0&&cA[i - 1] == cA[i]) KA++;
			//printf("%lld", res);
			add(&sA, two[N - i - 1]);
		}
		if (B[i + 1] == '0') {
			//printf("$");
			if (i>0&&cB[i - 1] == cB[i]) KB--;
			//printf("(%d %lld)\n", KB, sB);
			if (KB >= 0) res = (res - dp[i + 1][KB][cB[i] ? 1 : 0][1] - (sB+two[N-i-2]) * dp[i + 1][KB][cB[i] ? 1 : 0][0]) % MOD;
			if(KB>0) res = (res - dp[i + 1][KB-1][cB[i] ? 1 : 0][1] - (sB+two[N-i-2]) * dp[i + 1][KB-1][cB[i] ? 1 : 0][0]) % MOD;
			if (i>0&&cB[i - 1] == cB[i]) KB++;
			//printf("%lld", res);
		}
		else add(&sB, two[N - i - 2]);
		if (i > 0) {
			if (cA[i - 1] != cA[i]) KA--;
			if (cB[i - 1] != cB[i]) KB--;
		}
		res = (res + MOD) % MOD;
	}
	
	printf("%lld", res);
	return 0;
}

Compilation message

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:22: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:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s\n%s\n%s", ans, A, B);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 5 ms 4056 KB Output is correct
4 Correct 4 ms 3712 KB Output is correct
5 Correct 4 ms 3584 KB Output is correct
6 Correct 4 ms 3328 KB Output is correct
7 Correct 4 ms 3200 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 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 22 ms 22272 KB Output is correct
2 Correct 16 ms 16768 KB Output is correct
3 Correct 18 ms 18552 KB Output is correct
4 Correct 31 ms 31736 KB Output is correct
5 Correct 16 ms 16000 KB Output is correct
6 Correct 33 ms 31736 KB Output is correct
7 Correct 11 ms 11520 KB Output is correct
8 Correct 18 ms 18304 KB Output is correct
9 Correct 5 ms 4992 KB Output is correct
10 Correct 17 ms 17024 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4352 KB Output is correct
2 Correct 5 ms 4224 KB Output is correct
3 Correct 5 ms 4056 KB Output is correct
4 Correct 4 ms 3712 KB Output is correct
5 Correct 4 ms 3584 KB Output is correct
6 Correct 4 ms 3328 KB Output is correct
7 Correct 4 ms 3200 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Incorrect 1 ms 512 KB Output isn't correct
10 Halted 0 ms 0 KB -