#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 = 0; k <= n12; 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 = 0; k <= n21; 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 - 1][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
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);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
292 KB |
Output is correct |
| 3 |
Correct |
2 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
284 KB |
Output is correct |
| 6 |
Correct |
0 ms |
284 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
284 KB |
Output is correct |
| 9 |
Correct |
2 ms |
212 KB |
Output is correct |
| 10 |
Correct |
2 ms |
212 KB |
Output is correct |
| 11 |
Correct |
2 ms |
212 KB |
Output is correct |
| 12 |
Correct |
2 ms |
288 KB |
Output is correct |
| 13 |
Correct |
2 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
