Submission #21110183

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;

int H, W, A, B;
int ans;

int verify(const vector<int>& v) {
    int feasible = 1;
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            int p = v[h * W + w];
            if (p == 1) {
                if (w + 1 >= W) feasible = 0;
                if (w > 0 && v[h * W + w - 1] == 1) feasible = 0;
                if (h > 0) {
                    if (v[(h - 1) * W + w] == 2) feasible = 0;
                    if (v[(h - 1) * W + w + 1] == 2) feasible = 0;
                }
            } else if (p == 2) {
                if (h + 1 >= H) feasible = 0;
                if (h > 0 && v[(h - 1) * W + w] == 2) feasible = 0;
                if (w > 0 && v[h * W + w - 1] == 1) feasible = 0;
            }
            if (feasible == 0) break;
        }
    }
    return feasible;
}

void solve(int i, int cnt, const vector<int>& v) {
    if (cnt > A) return;
    if (i == H * W) {
        if (cnt == A) ans += verify(v);
        return;
    }
    auto v1 = v; v1.push_back(0);
    solve(i + 1, cnt, v1);
    if (i % W != W - 1) {
        auto v2 = v; v2.push_back(1);
        solve(i + 1, cnt + 1, v2);
    }
    if (i < (H - 1) * W) {
        auto v3 = v; v3.push_back(2);
        solve(i + 1, cnt + 1, v3);
    }
}

int main() {
    cin >> H >> W >> A >> B;
    solve(0, 0, vector<int>{});
    cout << ans << endl;
}

Submission Info

Submission Time
Task D - Hanjo
User gochiusa
Language C++ (Clang 10.0.0)
Score 400
Code Size 1460 Byte
Status AC
Exec Time 96 ms
Memory 3072 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 50
Set Name Test Cases
Sample 01_sample.txt, 02_sample.txt, 03_sample.txt
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_11.txt, 05_44.txt, 06_44.txt, 07_44.txt, 08_44.txt, 09_44.txt, 10_44.txt, 11_44.txt, 12_28.txt, 13_28.txt, 14_28.txt, 15_28.txt, 16_28.txt, 17_28.txt, 18_28.txt, 19_116.txt, 20_116.txt, 21_116.txt, 22_115.txt, 23_115.txt, 24_35.txt, 25_35.txt, 26_35.txt, 27_35.txt, 28_35.txt, 29_35.txt, 30_35.txt, 31_35.txt, 32_33.txt, 33_33.txt, 34_33.txt, 35_1x.txt, 36_1x.txt, 37_1x.txt, 38_1x.txt, 39_1x.txt, 40_1x.txt, 41_1x.txt, 42_1x.txt, 43_small.txt, 44_small.txt, 45_small.txt, 46_small.txt, 47_small.txt, 48_small.txt, 49_small.txt, 50_small.txt
Case Name Status Exec Time Memory
01_sample.txt AC 6 ms 2952 KiB
02_sample.txt AC 3 ms 2984 KiB
03_sample.txt AC 96 ms 3020 KiB
04_11.txt AC 2 ms 3032 KiB
05_44.txt AC 2 ms 2956 KiB
06_44.txt AC 2 ms 2968 KiB
07_44.txt AC 2 ms 2988 KiB
08_44.txt AC 5 ms 3036 KiB
09_44.txt AC 19 ms 2956 KiB
10_44.txt AC 40 ms 2956 KiB
11_44.txt AC 64 ms 2972 KiB
12_28.txt AC 2 ms 3000 KiB
13_28.txt AC 2 ms 2996 KiB
14_28.txt AC 15 ms 3024 KiB
15_28.txt AC 15 ms 3000 KiB
16_28.txt AC 24 ms 3000 KiB
17_28.txt AC 41 ms 3044 KiB
18_28.txt AC 55 ms 2956 KiB
19_116.txt AC 7 ms 2952 KiB
20_116.txt AC 2 ms 3020 KiB
21_116.txt AC 2 ms 2976 KiB
22_115.txt AC 8 ms 3024 KiB
23_115.txt AC 2 ms 3020 KiB
24_35.txt AC 2 ms 2952 KiB
25_35.txt AC 2 ms 2972 KiB
26_35.txt AC 2 ms 3036 KiB
27_35.txt AC 3 ms 3044 KiB
28_35.txt AC 7 ms 2976 KiB
29_35.txt AC 15 ms 3024 KiB
30_35.txt AC 22 ms 2988 KiB
31_35.txt AC 37 ms 3048 KiB
32_33.txt AC 2 ms 2996 KiB
33_33.txt AC 2 ms 3028 KiB
34_33.txt AC 2 ms 3000 KiB
35_1x.txt AC 2 ms 3020 KiB
36_1x.txt AC 2 ms 3020 KiB
37_1x.txt AC 2 ms 2956 KiB
38_1x.txt AC 2 ms 2988 KiB
39_1x.txt AC 2 ms 2964 KiB
40_1x.txt AC 3 ms 3072 KiB
41_1x.txt AC 3 ms 3020 KiB
42_1x.txt AC 2 ms 2956 KiB
43_small.txt AC 6 ms 3024 KiB
44_small.txt AC 2 ms 3040 KiB
45_small.txt AC 2 ms 2968 KiB
46_small.txt AC 9 ms 3000 KiB
47_small.txt AC 5 ms 3044 KiB
48_small.txt AC 2 ms 3036 KiB
49_small.txt AC 2 ms 3040 KiB
50_small.txt AC 2 ms 3000 KiB