oj.uz

Submission #374927

# Submission time Handle Problem Language Result Execution time Memory
374927 2021-03-08T14:49:18 Z Killer2501 마스코트 (JOI13_mascots) C++14
100 / 100
 1530 ms 207244 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "conststrfd"
#define pll pair<ll, ll>
#define pii pair<ll, pll>
#define fi first
#define se second
#define ull unsigned long long
using namespace std;
const ll mod = 1e9+7;
const ll N = 3005;
vector<ll> kq;
vector<pll> pre;
string s;
ll n, m, t, k, b[N*N], p, a[N*N], ans, tong, c, r, cnt;
ll dp[N][N];

ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

ll C(ll u, ll v)
{
    if(u > v)return 0;
    return a[v] * b[u] % mod * b[v-u]% mod;
}
void sol()
{
    cin >> r >> c >> n;
    a[0] = b[0]  = 1;
    for(int i = 1; i <= r*c; i ++)
    {
        a[i] = a[i-1] * i % mod;
        b[i] = b[i-1] * pw(i, mod-2) % mod;
    }
    ll posl = r, posr = c, posu = 1, posv = 1;
    for(int i = 1; i <= n;i ++)
    {
        ll u, v;
        cin >> u >> v;
        posl = min(posl, u);
        posu = max(posu, u);
        posr = min(posr, v);
        posv = max(posv, v);
    }
    ll u = posu-posl+1, v = posv-posr+1;
    dp[u][v] = a[u*v-n];
    for(int i = u; i <= r; i ++)
    {
        for(int j = v; j <= c; j ++)
        {
            if(i == u && j == v)continue;
            dp[i][j] = (dp[i-1][j] * a[j] + dp[i][j-1] * a[i]) % mod;

        }
    }
    //cout << dp[r][c] << '\n';
    cout << dp[r][c] * C(posl-1, r-u) % mod * C(posr-1, c-v) % mod;
}
int main()
{
    if(fopen(task".inp", "r")){
       freopen(task".inp", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    for(int i = 1; i <= ntest; i ++)
    sol();
}
/*
5
5 4
1 2
1 3
4 1
5 1
7 0
8 8
1 2
2 3
3 4
4 1
1 6
6 7
7 8
8 6
4 4
1 2
2 3
1 4
4 3
4 4
1 2
2 3
1 3
3 4
*/

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 620 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1004 KB Output is correct
2 Correct 14 ms 2156 KB Output is correct
3 Correct 16 ms 3180 KB Output is correct
4 Correct 141 ms 21868 KB Output is correct
5 Correct 139 ms 20972 KB Output is correct
6 Correct 178 ms 21220 KB Output is correct
7 Correct 289 ms 28908 KB Output is correct
8 Correct 632 ms 63084 KB Output is correct
9 Correct 1420 ms 141420 KB Output is correct
10 Correct 1274 ms 184684 KB Output is correct
11 Correct 1235 ms 162412 KB Output is correct
12 Correct 1264 ms 125164 KB Output is correct
13 Correct 107 ms 12524 KB Output is correct
14 Correct 1433 ms 141316 KB Output is correct
15 Correct 1530 ms 207244 KB Output is correct
16 Correct 1020 ms 144688 KB Output is correct
17 Correct 1424 ms 145728 KB Output is correct
18 Correct 1518 ms 204212 KB Output is correct