Submission #117921

#	Time	Username	Problem	Language	Result	Execution time	Memory
117921		onjo0127	Ljetopica (COI19_ljetopica)	C++11	17 / 100	104 ms	27776 KiB

ljetopica

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int N;
long long C[1009][1009][2], D[1009][1009][2], bi[1009];
char S[1009], A[1009], B[1009], H = ('L' ^ 'R');

void go(int idx, int left, bool ok) {
	long long &CC = C[idx][left][ok], &DD = D[idx][left][ok];

	if(idx == N) {
		if(left == 0) CC = DD = 1;
		else CC = DD = 0;
		return;
	}
	if(DD != -1) return;

	char X = S[idx];
	if(!ok) X ^= H;

	go(idx+1, left, ok);
	if(left) go(idx+1, left-1, !ok);

	CC = C[idx+1][left][ok];
	if(left) CC += C[idx+1][left-1][!ok];
	CC %= MOD;

	if(X == 'L') {
		DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx - 1] % MOD;
		DD %= MOD;
		if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx] % MOD, DD %= MOD;
	}
	else {
		DD = D[idx+1][left][ok] + C[idx+1][left][ok] * bi[N - idx] % MOD;
		DD %= MOD;
		if(left) DD += D[idx+1][left-1][!ok] + C[idx+1][left-1][!ok] * bi[N - idx - 1] % MOD, DD %= MOD;
	}
}

int main() {
    int K; scanf("%d%d",&N,&K);
    bi[0] = 1; for(int i=1; i<=N; i++) bi[i] = bi[i-1] * 2 % MOD;
    scanf(" %s %s %s", S+1, A, B);
   	memset(D, -1, sizeof(D));
    go(1, K, 1); go(1, K, 0);
    printf("%lld", (D[1][K][0] + D[1][K][1]) % MOD);
    return 0; 
}

Compilation message (stderr)

ljetopica.cpp: In function 'int main()':
ljetopica.cpp:43:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int K; scanf("%d%d",&N,&K);
            ~~~~~^~~~~~~~~~~~~~
ljetopica.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s %s %s", S+1, A, B);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 17 / 17
• Subtask 4: 0 / 61