Submission #2979127
Source Code Expand
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, std.bitmanip; immutable long MOD = 10^^9 + 7; bool valid(int mask) { return !((mask & (mask << 1)) || (mask & (mask >> 1))); } bool valid2(int mask1, int mask2) { return !((mask1 & (mask2 << 1)) || (mask1 & mask2) || (mask1 & (mask2 >> 1))); } void main() { auto s = readln.split.map!(to!int); auto H = s[0]; auto W = s[1]; auto masks = iota(1<<W).filter!(a => valid(a)).array; auto dp = new long[][](H+1, 1<<W); dp[0][0] = 1; foreach (r; 0..H) { foreach (mask1; masks) { if (dp[r][mask1] == 0) continue; foreach (mask2; masks) { if (!valid2(mask1, mask2)) continue; dp[r+1][mask2] += dp[r][mask1]; dp[r+1][mask2] %= MOD; } } } auto ans = (dp[H].sum - 1) % MOD; ans.writeln; }
Submission Info
Submission Time | |
---|---|
Task | A - 天下一有無 |
User | nebukuro09 |
Language | D (LDC 0.17.0) |
Score | 40 |
Code Size | 1048 Byte |
Status | AC |
Exec Time | 38 ms |
Memory | 4476 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 40 / 40 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | case0, case1, case10, case100, case101, case102, case103, case104, case105, case106, case107, case108, case109, case11, case110, case111, case112, case113, case114, case115, case116, case117, case118, case119, case12, case13, case14, case15, case16, case17, case18, case19, case2, case20, case21, case22, case23, case24, case25, case26, case27, case28, case29, case3, case30, case31, case32, case33, case34, case35, case36, case37, case38, case39, case4, case40, case41, case42, case43, case44, case45, case46, case47, case48, case49, case5, case50, case51, case52, case53, case54, case55, case56, case57, case58, case59, case6, case60, case61, case62, case63, case64, case65, case66, case67, case68, case69, case7, case70, case71, case72, case73, case74, case75, case76, case77, case78, case79, case8, case80, case81, case82, case83, case84, case85, case86, case87, case88, case89, case9, case90, case91, case92, case93, case94, case95, case96, case97, case98, case99 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
case0 | AC | 1 ms | 256 KB |
case1 | AC | 1 ms | 256 KB |
case10 | AC | 1 ms | 380 KB |
case100 | AC | 2 ms | 508 KB |
case101 | AC | 2 ms | 380 KB |
case102 | AC | 5 ms | 1020 KB |
case103 | AC | 2 ms | 508 KB |
case104 | AC | 25 ms | 3708 KB |
case105 | AC | 2 ms | 508 KB |
case106 | AC | 3 ms | 2428 KB |
case107 | AC | 6 ms | 1148 KB |
case108 | AC | 12 ms | 2812 KB |
case109 | AC | 27 ms | 3452 KB |
case11 | AC | 1 ms | 380 KB |
case110 | AC | 3 ms | 764 KB |
case111 | AC | 7 ms | 2684 KB |
case112 | AC | 13 ms | 2044 KB |
case113 | AC | 4 ms | 892 KB |
case114 | AC | 7 ms | 2812 KB |
case115 | AC | 8 ms | 3068 KB |
case116 | AC | 33 ms | 3964 KB |
case117 | AC | 16 ms | 2940 KB |
case118 | AC | 35 ms | 4220 KB |
case119 | AC | 38 ms | 4476 KB |
case12 | AC | 1 ms | 380 KB |
case13 | AC | 1 ms | 256 KB |
case14 | AC | 1 ms | 764 KB |
case15 | AC | 1 ms | 256 KB |
case16 | AC | 1 ms | 256 KB |
case17 | AC | 1 ms | 256 KB |
case18 | AC | 1 ms | 256 KB |
case19 | AC | 1 ms | 256 KB |
case2 | AC | 1 ms | 256 KB |
case20 | AC | 1 ms | 256 KB |
case21 | AC | 1 ms | 256 KB |
case22 | AC | 1 ms | 256 KB |
case23 | AC | 1 ms | 316 KB |
case24 | AC | 1 ms | 380 KB |
case25 | AC | 1 ms | 256 KB |
case26 | AC | 1 ms | 256 KB |
case27 | AC | 2 ms | 636 KB |
case28 | AC | 4 ms | 2428 KB |
case29 | AC | 1 ms | 256 KB |
case3 | AC | 1 ms | 256 KB |
case30 | AC | 1 ms | 256 KB |
case31 | AC | 1 ms | 256 KB |
case32 | AC | 1 ms | 256 KB |
case33 | AC | 1 ms | 256 KB |
case34 | AC | 1 ms | 256 KB |
case35 | AC | 1 ms | 256 KB |
case36 | AC | 1 ms | 256 KB |
case37 | AC | 1 ms | 256 KB |
case38 | AC | 2 ms | 380 KB |
case39 | AC | 1 ms | 256 KB |
case4 | AC | 1 ms | 256 KB |
case40 | AC | 3 ms | 764 KB |
case41 | AC | 1 ms | 256 KB |
case42 | AC | 1 ms | 256 KB |
case43 | AC | 1 ms | 256 KB |
case44 | AC | 1 ms | 256 KB |
case45 | AC | 1 ms | 256 KB |
case46 | AC | 1 ms | 256 KB |
case47 | AC | 1 ms | 380 KB |
case48 | AC | 1 ms | 256 KB |
case49 | AC | 1 ms | 256 KB |
case5 | AC | 1 ms | 256 KB |
case50 | AC | 2 ms | 508 KB |
case51 | AC | 3 ms | 2556 KB |
case52 | AC | 1 ms | 256 KB |
case53 | AC | 9 ms | 2428 KB |
case54 | AC | 1 ms | 256 KB |
case55 | AC | 1 ms | 256 KB |
case56 | AC | 1 ms | 256 KB |
case57 | AC | 1 ms | 256 KB |
case58 | AC | 1 ms | 380 KB |
case59 | AC | 1 ms | 380 KB |
case6 | AC | 1 ms | 256 KB |
case60 | AC | 1 ms | 380 KB |
case61 | AC | 1 ms | 256 KB |
case62 | AC | 2 ms | 256 KB |
case63 | AC | 1 ms | 256 KB |
case64 | AC | 1 ms | 256 KB |
case65 | AC | 1 ms | 256 KB |
case66 | AC | 1 ms | 256 KB |
case67 | AC | 1 ms | 256 KB |
case68 | AC | 1 ms | 256 KB |
case69 | AC | 1 ms | 380 KB |
case7 | AC | 1 ms | 256 KB |
case70 | AC | 2 ms | 380 KB |
case71 | AC | 1 ms | 256 KB |
case72 | AC | 1 ms | 256 KB |
case73 | AC | 1 ms | 256 KB |
case74 | AC | 14 ms | 2812 KB |
case75 | AC | 1 ms | 256 KB |
case76 | AC | 1 ms | 256 KB |
case77 | AC | 1 ms | 380 KB |
case78 | AC | 1 ms | 256 KB |
case79 | AC | 1 ms | 256 KB |
case8 | AC | 1 ms | 256 KB |
case80 | AC | 1 ms | 256 KB |
case81 | AC | 4 ms | 2684 KB |
case82 | AC | 8 ms | 1404 KB |
case83 | AC | 1 ms | 256 KB |
case84 | AC | 1 ms | 256 KB |
case85 | AC | 1 ms | 380 KB |
case86 | AC | 1 ms | 380 KB |
case87 | AC | 1 ms | 380 KB |
case88 | AC | 3 ms | 636 KB |
case89 | AC | 4 ms | 892 KB |
case9 | AC | 1 ms | 256 KB |
case90 | AC | 9 ms | 1532 KB |
case91 | AC | 1 ms | 380 KB |
case92 | AC | 1 ms | 380 KB |
case93 | AC | 1 ms | 380 KB |
case94 | AC | 2 ms | 508 KB |
case95 | AC | 3 ms | 636 KB |
case96 | AC | 5 ms | 1020 KB |
case97 | AC | 10 ms | 3452 KB |
case98 | AC | 22 ms | 4092 KB |
case99 | AC | 1 ms | 380 KB |