Submission #1197136

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197136		DarkCyann_	마스코트 (JOI13_mascots)	C++20	0 / 100	964 ms	1196 KiB

mascots

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 9000000;
int fact[MAX + 1];

void init_factorials(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = 1LL * fact[i - 1] * i % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C;
    cin >> R >> C;
    int N;
    cin >> N;

    vector<vector<int>> grid(R + 1, vector<int>(C + 1, 0));
    set<pair<int, int>> initial;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        grid[a][b] = 1;
        initial.insert({a, b});
    }

    // Prefix sum grid
    vector<vector<int>> psum(R + 2, vector<int>(C + 2, 0));
    for (int i = 1; i <= R; ++i)
        for (int j = 1; j <= C; ++j)
            psum[i][j] = grid[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];

    // Function to get sum in rectangle (r1, c1) to (r2, c2)
    auto get_sum = [&](int r1, int c1, int r2, int c2) {
        return psum[r2][c2] - psum[r1-1][c2] - psum[r2][c1-1] + psum[r1-1][c1-1];
    };

    int max_happy = 0;
    unordered_map<int, int> count;  // happy_count -> number of ways

    init_factorials(R * C);

    // Enumerate all rectangles
    for (int r1 = 1; r1 <= R; ++r1) {
        for (int r2 = r1; r2 <= R; ++r2) {
            for (int c1 = 1; c1 <= C; ++c1) {
                for (int c2 = c1; c2 <= C; ++c2) {
                    int area = (r2 - r1 + 1) * (c2 - c1 + 1);
                    int inside = get_sum(r1, c1, r2, c2);

                    // Must contain all initial mascots
                    if (inside != N) continue;

                    // Check all initial mascots are inside
                    bool valid = true;
                    for (auto [x, y] : initial) {
                        if (x < r1 || x > r2 || y < c1 || y > c2) {
                            valid = false;
                            break;
                        }
                    }
                    if (!valid) continue;

                    int empty_inside = area - N;
                    count[empty_inside] = (count[empty_inside] + fact[empty_inside]) % MOD;
                    max_happy = max(max_happy, empty_inside);
                }
            }
        }
    }

    cout << count[max_happy] << '\n';
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60