Submission #123302
Source Code Expand
#include <stdio.h> long long dp[2][120][120][16]; long long comb[1000][1000]; int main() { int r, c, x, y, d, l, z, mod = 1000000007, i, j, k, p; long long ans = 0; scanf("%d %d", &r, &c); scanf("%d %d", &x, &y); scanf("%d %d", &d, &l); for (i = 0; i < 1000; i++) { comb[i][0] = comb[i][i] = 1; for (j = 1; j < i; j++) comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % mod; } if (x == 1 && y == 1) { printf("%d\n", r * c); return 0; } else if (x == 1 || y == 1) { if (d >= 2) ans = (ans + comb[x + y - 3][d - 2] * comb[x + y - d - 1][l] % mod) % mod; if (l >= 2) ans = (ans + comb[x + y - 3][l - 2] * comb[x + y - l - 1][d] % mod) % mod; if (d >= 1 && l >= 1) ans = (ans + comb[x + y - 3][d - 1] * comb[x + y - d - 2][l - 1] * 2 % mod) % mod; ans = ans * (r - x + 1) * (c - y + 1) % mod; printf("%lld\n", ans); return 0; } dp[0][0][0][0] = 1; for (i = 0; i < x * 2 + y * 2 - 4; i++) { for (j = 0; j <= d && j <= i; j++) { for (k = 0; k <= l && k <= i; k++) { for (p = 0; p < 16; p++) { int c = 0; if (dp[i & 1][j][k][p] == 0) continue; if (i <= x - 1) c |= 1; if (i >= x - 1 && i <= x + y - 2) c |= 2; if (i >= x + y - 2 && i <= x * 2 + y - 3) c |= 4; if (i >= x * 2 + y - 3 || i == 0) c |= 8; dp[(i + 1) & 1][j][k][p] = (dp[(i + 1) & 1][j][k][p] + dp[i & 1][j][k][p]) % mod; if (j < d) dp[(i + 1) & 1][j + 1][k][p | c] = (dp[(i + 1) & 1][j + 1][k][p | c] + dp[i & 1][j][k][p]) % mod; if (k < l) dp[(i + 1) & 1][j][k + 1][p | c] = (dp[(i + 1) & 1][j][k + 1][p | c] + dp[i & 1][j][k][p]) % mod; dp[i & 1][j][k][p] = 0; } } } } z = x * y - x * 2 - y * 2 + 4; for (i = 0; i <= d && i <= x * 2 + y * 2 - 4; i++) { for (j = 0; j <= l && j <= x * 2 + y * 2 - 4; j++) { if (dp[(x * 2 + y * 2 - 4) & 1][i][j][15] == 0) continue; if (d - i + l - j > z) continue; ans = (ans + dp[(x * 2 + y * 2 - 4) & 1][i][j][15] * comb[z][d - i] % mod * comb[z - d + i][l - j] % mod) % mod; } } ans = ans * (r - x + 1) * (c - y + 1) % mod; printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - AtCoder社の冬 |
User | kawatea |
Language | C (GCC 4.6.4) |
Score | 101 |
Code Size | 2762 Byte |
Status | AC |
Exec Time | 55 ms |
Memory | 9248 KB |
Compile Error
./Main.c: In function ‘main’: ./Main.c:11:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] ./Main.c:12:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] ./Main.c:13:10: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
Judge Result
Set Name | sub | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 100 / 100 | 1 / 1 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
sub | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, test_03E.txt, test_04E.txt, test_07E.txt, test_08E.txt, test_11E.txt, test_12E.txt, test_15E.txt, test_16E.txt, test_19E.txt, test_20E.txt, test_23E.txt, test_24E.txt, test_27E.txt, test_28E.txt, test_31E.txt, test_32E.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_45E.txt, test_47E.txt |
All | 00_sample_01E.txt, 00_sample_02E.txt, 00_sample_03E.txt, 00_sample_04.txt, test_01.txt, test_02.txt, test_03E.txt, test_04E.txt, test_05.txt, test_06.txt, test_07E.txt, test_08E.txt, test_09.txt, test_10.txt, test_11E.txt, test_12E.txt, test_13.txt, test_14.txt, test_15E.txt, test_16E.txt, test_17.txt, test_18.txt, test_19E.txt, test_20E.txt, test_21.txt, test_22.txt, test_23E.txt, test_24E.txt, test_25.txt, test_26.txt, test_27E.txt, test_28E.txt, test_29.txt, test_30.txt, test_31E.txt, test_32E.txt, test_33.txt, test_34.txt, test_35.txt, test_36E.txt, test_37E.txt, test_38E.txt, test_39E.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45E.txt, test_46.txt, test_47E.txt, test_48.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_01E.txt | AC | 31 ms | 7592 KB |
00_sample_02E.txt | AC | 31 ms | 7588 KB |
00_sample_03E.txt | AC | 36 ms | 8348 KB |
00_sample_04.txt | AC | 55 ms | 9248 KB |
test_01.txt | AC | 31 ms | 7584 KB |
test_02.txt | AC | 30 ms | 7704 KB |
test_03E.txt | AC | 30 ms | 7716 KB |
test_04E.txt | AC | 31 ms | 7592 KB |
test_05.txt | AC | 31 ms | 7584 KB |
test_06.txt | AC | 32 ms | 7716 KB |
test_07E.txt | AC | 31 ms | 7592 KB |
test_08E.txt | AC | 31 ms | 7592 KB |
test_09.txt | AC | 31 ms | 7592 KB |
test_10.txt | AC | 31 ms | 7592 KB |
test_11E.txt | AC | 30 ms | 7588 KB |
test_12E.txt | AC | 31 ms | 7528 KB |
test_13.txt | AC | 31 ms | 7524 KB |
test_14.txt | AC | 32 ms | 7580 KB |
test_15E.txt | AC | 31 ms | 7588 KB |
test_16E.txt | AC | 32 ms | 7588 KB |
test_17.txt | AC | 31 ms | 7592 KB |
test_18.txt | AC | 31 ms | 7596 KB |
test_19E.txt | AC | 30 ms | 7596 KB |
test_20E.txt | AC | 30 ms | 7588 KB |
test_21.txt | AC | 30 ms | 7592 KB |
test_22.txt | AC | 31 ms | 7576 KB |
test_23E.txt | AC | 31 ms | 7520 KB |
test_24E.txt | AC | 32 ms | 7592 KB |
test_25.txt | AC | 31 ms | 7544 KB |
test_26.txt | AC | 32 ms | 7588 KB |
test_27E.txt | AC | 32 ms | 7588 KB |
test_28E.txt | AC | 30 ms | 7584 KB |
test_29.txt | AC | 31 ms | 7588 KB |
test_30.txt | AC | 32 ms | 7588 KB |
test_31E.txt | AC | 30 ms | 7576 KB |
test_32E.txt | AC | 31 ms | 7584 KB |
test_33.txt | AC | 31 ms | 7596 KB |
test_34.txt | AC | 32 ms | 7968 KB |
test_35.txt | AC | 31 ms | 7524 KB |
test_36E.txt | AC | 31 ms | 7588 KB |
test_37E.txt | AC | 31 ms | 7720 KB |
test_38E.txt | AC | 30 ms | 7592 KB |
test_39E.txt | AC | 30 ms | 7584 KB |
test_40.txt | AC | 30 ms | 7584 KB |
test_41.txt | AC | 30 ms | 7584 KB |
test_42.txt | AC | 33 ms | 7972 KB |
test_43.txt | AC | 30 ms | 7588 KB |
test_44.txt | AC | 34 ms | 7972 KB |
test_45E.txt | AC | 31 ms | 7584 KB |
test_46.txt | AC | 31 ms | 7648 KB |
test_47E.txt | AC | 31 ms | 7592 KB |
test_48.txt | AC | 31 ms | 7544 KB |