Submission #117809

#	Time	Username	Problem	Language	Result	Execution time	Memory
117809		ainta	Ljetopica (COI19_ljetopica)	C++17	100 / 100	220 ms	24184 KiB

ljetopica

#include<cstdio>
#include<algorithm>
using namespace std;
int n, K, chk[1010], C[1010][1010][2];
long long S[1010][1010][2], Mod = 1000000007;
char p[1010], B[1010], E[1010];
int Get(char *T) {
	int i, j, k, l, c = 0;
	for (i = 0; i <= n; i++)for (j = 0; j <= n; j++)S[i][j][0] = S[i][j][1] = 0, C[i][j][0] = C[i][j][1] = 0;
	long long s = 1;
	for (i = 0; i < n; i++) {
		if (T[i] == '1') {
			int t = c;
			if (i && (T[i - 1] == '1') != (chk[i] == 1))t++;
			C[i + 1][t][0] = (C[i + 1][t][0] + 1)%Mod;
			S[i + 1][t][0] = (S[i + 1][t][0] + s * 2 % Mod) % Mod;
		}
		if (i)c += ((T[i] != T[i - 1]) != (chk[i] == 1));
		s = (s * 2 + T[i] - '0') % Mod;
		for (j = 0; j <= i; j++) {
			for (k = 0; k < 2; k++) {
				for (l = 0; l < 2; l++) {
					int ck = 0;
					if ((k != l) != (chk[i] == 1))ck = 1;
					C[i + 1][j+ck][k] = (C[i + 1][j+ck][k] + C[i][j][l]) % Mod;
					S[i + 1][j+ck][k] = (S[i + 1][j+ck][k] + S[i][j][l] * 2 + k * C[i][j][l]) % Mod;
				}
			}
		}
	}
	S[n][c][T[n - 1]-'0'] += s;
	long long res = S[n][K][0] + S[n][K][1];
	if (K)res += S[n][K - 1][0] + S[n][K - 1][1];
	return res % Mod;
}
int main() {
	int i, j;
	scanf("%d%d", &n, &K);
	scanf("%s%s%s", p,B,E);
	n--;
	for (i = 1; i < n; i++) {
		if (p[i] != p[i - 1])chk[i] = 1;
	}
	int res = Get(E+1);
	for (i = n; i >= 0; i--) {
		if (B[i] == '1')break;
	}
	if (i) {
		for (j = i + 1; j <= n; j++)B[j] = '1';
		B[i] = '0';
		res = (res+Mod-Get(B+1))%Mod;
	}
	printf("%d\n", res);
}

Compilation message (stderr)

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

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