Submission #1110731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110731		ljtunas	마스코트 (JOI13_mascots)	C++17	100 / 100	128 ms	69192 KiB

mascots

#include <bits/stdc++.h>// "i will win voi25"
using namespace std;

#define fi first
#define se second
#define Forv(v, h)    for(auto &v : h)
#define For(i, a, b)  for(int i = a; i <= b; ++i)
#define Ford(i, a, b) for(int i = a; i >= b; --i)
#define all(h)        h.begin(), h.end()
#define reset(h, v)   (memset(h, v, sizeof(h)))
#define c_bit(i)       __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))

using ll  = long long;
using ii  = pair<ll, ll>;
using vi  = vector<ll>;
using vvi = vector<vi>;
using vii = vector<ii>;

template <class X, class Y> bool maximize(X &a, const Y &b)
{
    if(a < b) return a = b, true;
    return false;
}

template <class X, class Y> bool minimize(X &a, const Y &b)
{
    if(a > b) return a = b, true;
    return false;
}

 #define int long long

const int dx[] = {0, -1, +1, 0}, dy[] = {-1, 0, 0, +1};
const ll oo = 1e18 + 1, base = 311, block = 500;
const ll MOD = 1e9 + 7;
const int MAXN = 3e3  + 5;

ll Pow(ll a, ll n) {
    ll res = 1;
    while (n) {
        if (n & 1) res = 1ll * (res * a) % MOD;
        a = 1ll * (a * a) % MOD, n >>= 1;
    }
    return res;
}

struct Ckn {
    const static int maxn = 1e5 + 100;
    ll fac[maxn], ifac[maxn];
    void init(int n) {
        fac[0] = 1; For(i, 1, n) fac[i] = (1ll * i * fac[i - 1]) % MOD;

        ifac[n - 1] = Pow(fac[n - 1], MOD - 2);

        Ford(i, n - 2, 0) ifac[i] = (1ll * (i + 1) * ifac[i + 1]) % MOD;
    }
    long long ckn(long long r, long long n){
        return fac[n] * ifac[r] % MOD * ifac[n - r] % MOD;
    }
    //             (k, n) = 0 if k > n
    //             (k, n) = n * nf[k] * (k - 1, n - 1)
    //       sigma (i, n) = 2 ^ n              :i = 0 -> n
    //       sigma (k, i) = (k + 1, n + 1)     :i = 0 -> n
    //  sigma (i, n + i)  = (m, n + m + 1)     :i = 0 -> m
    // sigma {(i, n) ^ 2} = (n, 2n)            :i = 0 -> n
    // sigma {k * (k, n)} = n * 2 ^ (n - 1)    :i = 1 -> n
    // x[1] + x[2] + .. + x[n]  = m (x[i] >= 0) => (n - 1, m + n - 1)
    // x[1] + x[2] + .. + x[n] <= m (x[i] >= 0) => (n, m + n)
    // cell(u, v) -> cell(x, y) => (x - u, x + y - u - v)
} C;

int r, c, n;
ll dp[MAXN][MAXN];

void process()
{
    cin >> r >> c >> n;
    int x = r, y = c, u = 1, v = 1;
    For (i, 1, n) {
        int posx, posy;
        cin >> posx >> posy;
        minimize(x, posx), minimize(y, posy);
        maximize(u, posx), maximize(v, posy);
    }

    C.init(1e5);

    int h = u - x + 1, w = v - y + 1;
    dp[h][w] = 1;
    For (i, 2, h * w - n) (dp[h][w] *= 1ll * i) %= MOD;
    ll res = (C.ckn(x - 1, r - h) * C.ckn(y - 1, c - w)) % MOD;
    For (i, h, r) For (j, w, c)
    {
        if (i == h && j == w) continue;
        (dp[i][j] += (dp[i - 1][j] * C.fac[j]) % MOD) %= MOD;
        (dp[i][j] += (dp[i][j - 1] * C.fac[i]) % MOD) %= MOD;
    }
    cout << (res * dp[r][c]) % MOD;

    return void();
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define name "a"
    if (fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
    //int tc = 1; cin >> tc; while (tc--)
    process(); // -> ac
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s.\n";
    return 0;
}

Compilation message (stderr)

mascots.cpp: In function 'int32_t main()':
mascots.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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