oj.uz

Submission #34939

# Submission time Handle Problem Language Result Execution time Memory
34939 2017-11-17T08:34:01 Z ztrong 마스코트 (JOI13_mascots) C++14
0 / 100
 0 ms 72724 KB 
#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;

    int ha = getHash(xl, xr, yl, yr);
    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;
    return res;
}

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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 72724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 72724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 72724 KB Output isn't correct
2 Halted 0 ms 0 KB -