Submission #703468

#	Time	Username	Problem	Language	Result	Execution time	Memory
703468		Cyanmond	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	0 ms	212 KiB

amusementpark

#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod = 998244353;

void chmin(int &a, int b) {
    if (a > b) a = b;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::pair<int, int>> slides(M);
    std::vector<std::vector<int>> status(N, std::vector<int>(N));
    for (auto &[a, b] : slides) {
        std::cin >> a >> b;
        --a, --b;
        status[a][b] = 1;
        status[b][a] = 2;
    }
    // n = 15 ?
    std::vector<i64> dp1(1 << N, 0), dp2(1 << N, 0);
    dp1[0] = 1;
    for (int bits = 0; bits < (1 << N); ++bits) {
        for (int nextBit = 0; nextBit < N; ++nextBit) {
            if (bits & (1 << nextBit)) {
                continue;
            }
            const int nextBits = bits | (1 << nextBit);
            // calc cost
            i64 cost = 0;
            for (int i = 0; i < N; ++i) {
                if (not(bits & (1 << i))) {
                    continue;
                }
                if (status[i][nextBit] == 1) {
                    ++cost;
                }
            }
            dp2[nextBits] += dp2[bits] + cost * dp1[bits];
            dp1[nextBits] += dp1[bits];
            dp2[nextBits] %= mod;
            dp1[nextBits] %= mod;
        }
    }
    std::cout << dp2[(1 << N) - 1] % mod << std::endl;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37