oj.uz

Submission #34959

# Submission time Handle Problem Language Result Execution time Memory
34959 2017-11-17T08:53:27 Z ztrong 마스코트 (JOI13_mascots) C++14
40 / 100
 2000 ms 262144 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;

    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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72724 KB Output is correct
2 Correct 0 ms 72724 KB Output is correct
3 Correct 0 ms 72724 KB Output is correct
4 Correct 0 ms 72724 KB Output is correct
5 Correct 0 ms 72724 KB Output is correct
6 Correct 0 ms 72724 KB Output is correct
7 Correct 0 ms 72724 KB Output is correct
8 Correct 0 ms 72724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72724 KB Output is correct
2 Correct 0 ms 72724 KB Output is correct
3 Correct 0 ms 72724 KB Output is correct
4 Correct 0 ms 72856 KB Output is correct
5 Correct 3 ms 73168 KB Output is correct
6 Correct 0 ms 72724 KB Output is correct
7 Correct 0 ms 72724 KB Output is correct
8 Correct 0 ms 72724 KB Output is correct
9 Correct 13 ms 74448 KB Output is correct
10 Correct 0 ms 72856 KB Output is correct
11 Correct 0 ms 72724 KB Output is correct
12 Correct 0 ms 72724 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72724 KB Output is correct
2 Execution timed out 2000 ms 262144 KB Execution timed out
3 Halted 0 ms 0 KB -