제출 #1302495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302495		vukhacminh	마스코트 (JOI13_mascots)	C++20	10 / 100	2095 ms	1160 KiB

mascots

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C;
    if(!(cin >> R >> C)) return 0;
    int N; cin >> N;
    int RC = R * C;
    vector<char> init(RC, 0);
    for(int i = 0; i < N; ++i){
        int a,b; cin >> a >> b; // 1-based
        --a; --b;
        init[a*C + b] = 1;
    }
    vector<int> empties;
    for(int idx = 0; idx < RC; ++idx) if(!init[idx]) empties.push_back(idx);
    int k = (int)empties.size();

    // enumerate permutations of indices 0..k-1
    vector<int> perm(k);
    iota(perm.begin(), perm.end(), 0);
    ll best = -1;
    ll ways = 0;

    if(k == 0){
        // không có ô trống (theo đề ít nhất có 1 ô trống), nhưng xử lý an toàn:
        cout << 1 % MOD << '\n';
        return 0;
    }

    // for each permutation
    do {
        vector<char> occ = init;
        int occCount = 0;
        for(char v : occ) if(v) ++occCount;
        ll happy = 0;
        for(int step = 0; step < k; ++step){
            int pos = empties[perm[step]];
            occ[pos] = 1;
            ++occCount;
            // find bounding rectangle of occupied cells
            int minr = R, maxr = -1, minc = C, maxc = -1;
            for(int idx = 0; idx < RC; ++idx){
                if(occ[idx]){
                    int r = idx / C;
                    int c = idx % C;
                    minr = min(minr, r);
                    maxr = max(maxr, r);
                    minc = min(minc, c);
                    maxc = max(maxc, c);
                }
            }
            if(maxr >= 0){
                int area = (maxr - minr + 1) * (maxc - minc + 1);
                if(area == occCount) ++happy;
            }
        }
        if(happy > best){
            best = happy;
            ways = 1;
        } else if(happy == best){
            ++ways;
            if(ways >= MOD) ways -= MOD;
        }
    } while(next_permutation(perm.begin(), perm.end()));

    cout << (ways % MOD) << '\n';
    return 0;
}

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