Submission #34959

#	Time	Username	Problem	Language	Result	Execution time	Memory
34959		ztrong	마스코트 (JOI13_mascots)	C++14	40 / 100	2000 ms	262144 KiB

mascots

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

#define llint long long

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #else
    //freopen("name.inp", "r", stdin);
    //freopen("name.out", "w", stdout);
    #endif
}

const int maxN = 3e3 + 5;
const int maxM = 1e6 + 5;
const llint INF = 1e9 + 7;

int N, R, C;
int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
llint gt[maxN * maxN];
unordered_map<llint, llint> f;

void enter() {
    cin >> R >> C;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int x, y;
        cin >> x >> y;
        xmin = min(xmin, x);
        xmax = max(xmax, x);
        ymin = min(ymin, y);
        ymax = max(ymax, y);
    }
}

inline llint getHash(int x, int y, int z, int t) {
    return 1ll * (x - 1) * 10000 * 10000 * 10000
        + 1ll * (y - 1) * 10000 * 10000
        + 1ll * (z - 1) * 10000
        + 1ll * (t - 1);
}

llint getf(int xl, int xr, int yl, int yr) {
    if (xl > xmin || xr < xmax) return 0;
    if (yl > ymin || yr < ymax) return 0;

    llint ha = getHash(xl, xr, yl, yr);
    //cout << xl << " " << xr << " " << yl << " " << yr << " " << endl;
    if (f.count(ha)) {
        return f[ha];
    }
    llint res = 0;
    res = (res + gt[xr - xl + 1] * getf(xl, xr, yl + 1, yr)) % INF;
    res = (res + gt[xr - xl + 1] * getf(xl, xr, yl, yr - 1)) % INF;
    res = (res + gt[yr - yl + 1] * getf(xl + 1, xr, yl, yr)) % INF;
    res = (res + gt[yr - yl + 1] * getf(xl, xr - 1, yl, yr)) % INF;
    f[ha] = res;
    //cout << res << endl;
    return res;
}

void solve() {
    gt[0] = 1;
    for (int i = 1; i <= R * C; ++i) {
        gt[i] = gt[i - 1] * i % INF;
    }
    //cout << xmin << " " << xmax << " " << ymin << " " << ymax << endl;
    f[getHash(xmin, xmax, ymin, ymax)] = gt[(xmax - xmin + 1) * (ymax - ymin + 1) - N];
    //cout << getHash(xmin, xmax, ymin, ymax) << endl;
    cout << getf(1, R, 1, C) << endl;
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

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