oj.uz

Submission #1110731

# Submission time Handle Problem Language Result Execution time Memory
1110731 2024-11-10T09:39:51 Z ljtunas 마스코트 (JOI13_mascots) C++17
100 / 100
 128 ms 69192 KB 
#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

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

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 2 ms 4856 KB Output is correct
3 Correct 2 ms 4688 KB Output is correct
4 Correct 3 ms 2640 KB Output is correct
5 Correct 2 ms 2640 KB Output is correct
6 Correct 3 ms 4856 KB Output is correct
7 Correct 2 ms 4688 KB Output is correct
8 Correct 2 ms 4688 KB Output is correct
9 Correct 3 ms 2908 KB Output is correct
10 Correct 3 ms 2640 KB Output is correct
11 Correct 3 ms 4688 KB Output is correct
12 Correct 2 ms 4688 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4688 KB Output is correct
2 Correct 3 ms 4688 KB Output is correct
3 Correct 4 ms 5968 KB Output is correct
4 Correct 15 ms 13060 KB Output is correct
5 Correct 14 ms 12028 KB Output is correct
6 Correct 23 ms 9808 KB Output is correct
7 Correct 7 ms 5456 KB Output is correct
8 Correct 3 ms 4688 KB Output is correct
9 Correct 36 ms 3152 KB Output is correct
10 Correct 120 ms 68932 KB Output is correct
11 Correct 82 ms 49004 KB Output is correct
12 Correct 46 ms 3440 KB Output is correct
13 Correct 6 ms 6480 KB Output is correct
14 Correct 44 ms 3064 KB Output is correct
15 Correct 128 ms 69192 KB Output is correct
16 Correct 93 ms 53728 KB Output is correct
17 Correct 42 ms 9388 KB Output is correct
18 Correct 119 ms 67132 KB Output is correct