Submission #793441

#	Time	Username	Problem	Language	Result	Execution time	Memory
793441		rainboy	Long puzzle (innopolis2021_final_D)	C11	100 / 100	39 ms	628 KiB

Main

#include <stdio.h>
#include <string.h>

#define N	300
#define M	300
#define MD	1000000007

int main() {
	static int dp01[M + 1], dp02[M + 1];
	static int dp10[M + 1], dp20[M + 1];
	static int dp11[M + 1], dp22[M + 1];
	static int dp12[N + 1][M + 1], dp21[N + 1][M + 1];
	static int dp[M + 1], dq[M + 1];
	int n, n12, n21, m, k, i, s01, s02, s10, s20, s11, s22, s12, s21, s, s_, ans;

	scanf("%d%d", &n, &m);
	ans = 0;
	dp11[0] = dp22[0] = 1;
	dp12[0][0] = 1, n12 = 0;
	dp21[0][0] = 1, n21 = 0;
	for (i = 0; i < n; i++) {
		static char aa[5], bb[5];
		int l, a, b;

		scanf("%d%s%s", &l, aa, bb);
		a = aa[0] == 'n' ? 0 : (aa[0] == 'i' ? 1 : 2);
		b = bb[0] == 'n' ? 0 : (bb[0] == 'i' ? 2 : 1);
		if (a == 0 && b == 0) {
			if (l == m)
				ans++;
			continue;
		}
		if (a == 0 && b == 1)
			dp01[l]++;
		else if (a == 0 && b == 2)
			dp02[l]++;
		else if (a == 1 && b == 0)
			dp10[l]++;
		else if (a == 2 && b == 0)
			dp20[l]++;
		else if (a == 1 && b == 1) {
			for (s11 = m; s11 >= l; s11--)
				if ((dp11[s11] += dp11[s11 - l]) >= MD)
					dp11[s11] -= MD;
		} else if (a == 2 && b == 2) {
			for (s22 = m; s22 >= l; s22--)
				if ((dp22[s22] += dp22[s22 - l]) >= MD)
					dp22[s22] -= MD;
		} else if (a == 1 && b == 2) {
			for (k = n12; k >= 0; k--)
				for (s12 = 0; (s_ = s12 + l) <= m; s12++)
					if ((dp12[k + 1][s_] += dp12[k][s12]) >= MD)
						dp12[k + 1][s_] -= MD;
			n12++;
		} else if (a == 2 && b == 1) {
			for (k = n21; k >= 0; k--)
				for (s21 = 0; (s_ = s21 + l) <= m; s21++)
					if ((dp21[k + 1][s_] += dp21[k][s21]) >= MD)
						dp21[k + 1][s_] -= MD;
			n21++;
		}
	}
	memset(dp, 0, (m + 1) * sizeof *dp);
	for (k = 1; k <= n12 && k - 1 <= n21; k++)
		for (s12 = 0; s12 <= m; s12++)
			for (s21 = 0; (s_ = s12 + s21) <= m; s21++)
				dp[s_] = (dp[s_] + (long long) dp12[k][s12] * dp21[k - 1][s21]) % MD;
	memset(dq, 0, (m + 1) * sizeof *dq);
	for (s01 = 0; s01 <= m; s01++)
		for (s20 = 0; (s_ = s01 + s20) <= m; s20++)
			dq[s_] = (dq[s_] + (long long) dp01[s01] * dp20[s20]) % MD;
	for (s = m; s >= 0; s--)
		for (s11 = 1; (s_ = s + s11) <= m; s11++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp11[s11]) % MD;
	for (s = m; s >= 0; s--)
		for (s22 = 1; (s_ = s + s22) <= m; s22++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp22[s22]) % MD;
	for (s = 0; s <= m; s++)
		ans = (ans + (long long) dp[s] * dq[m - s]) % MD;
	memset(dp, 0, (m + 1) * sizeof *dp);
	for (k = 1; k <= n21 && k - 1 <= n12; k++)
		for (s21 = 0; s21 <= m; s21++)
			for (s12 = 0; (s_ = s21 + s12) <= m; s12++)
				dp[s_] = (dp[s_] + (long long) dp21[k][s21] * dp12[k - 1][s12]) % MD;
	memset(dq, 0, (m + 1) * sizeof *dq);
	for (s02 = 0; s02 <= m; s02++)
		for (s10 = 0; (s_ = s02 + s10) <= m; s10++)
			dq[s_] = (dq[s_] + (long long) dp02[s02] * dp10[s10]) % MD;
	for (s = m; s >= 0; s--)
		for (s22 = 1; (s_ = s + s22) <= m; s22++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp22[s22]) % MD;
	for (s = m; s >= 0; s--)
		for (s11 = 1; (s_ = s + s11) <= m; s11++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp11[s11]) % MD;
	for (s = 0; s <= m; s++)
		ans = (ans + (long long) dp[s] * dq[m - s]) % MD;
	memset(dp, 0, (m + 1) * sizeof *dp);
	for (k = 1; k <= n12 && k <= n21; k++)
		for (s12 = 0; s12 <= m; s12++)
			for (s21 = 0; (s_ = s12 + s21) <= m; s21++)
				dp[s_] = (dp[s_] + (long long) dp12[k][s12] * dp21[k][s21]) % MD;
	memset(dq, 0, (m + 1) * sizeof *dq);
	for (s01 = 0; s01 <= m; s01++)
		for (s10 = 0; (s_ = s01 + s10) <= m; s10++)
			dq[s_] = (dq[s_] + (long long) dp01[s01] * dp10[s10]) % MD;
	for (s02 = 0; s02 <= m; s02++)
		for (s20 = 0; (s_ = s02 + s20) <= m; s20++)
			dq[s_] = (dq[s_] + (long long) dp02[s02] * dp20[s20]) % MD;
	for (s = m; s >= 0; s--)
		for (s11 = 1; (s_ = s + s11) <= m; s11++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp11[s11]) % MD;
	for (s = m; s >= 0; s--)
		for (s22 = 1; (s_ = s + s22) <= m; s22++)
			dq[s_] = (dq[s_] + (long long) dq[s] * dp22[s22]) % MD;
	for (s = 0; s <= m; s++)
		ans = (ans + (long long) dp[s] * dq[m - s]) % MD;
	for (s01 = 0; s01 <= m; s01++)
		for (s10 = 0; s01 + s10 <= m; s10++) {
			s11 = m - s01 - s10;
			ans = (ans + (long long) dp01[s01] * dp10[s10] % MD * dp11[s11]) % MD;
		}
	for (s02 = 0; s02 <= m; s02++)
		for (s20 = 0; s02 + s20 <= m; s20++) {
			s22 = m - s02 - s20;
			ans = (ans + (long long) dp02[s02] * dp20[s20] % MD * dp22[s22]) % MD;
		}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

Main.c: In function 'main':
Main.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%d%s%s", &l, aa, bb);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20