| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 26410 |
2017-06-30T04:38:01 Z |
zscoder |
마스코트 (JOI13_mascots) |
C++14 |
|
336 ms |
230460 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
const ll MOD = 1e9 + 7;
ll fact[10000001];
ll rl, rr, cl, cr;
ll choose[3100][3100];
ll dp[3100][3100];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
ll r, c; cin>>r>>c;
ll n; cin>>n;
ll rmin, rmax, cmin, cmax;
rmin = r+1; rmax = 0; cmin = c+1; cmax = 0;
for(ll i = 0; i < n; i++)
{
ll x, y;
cin >> x >> y;
rmin = min(x, rmin);
rmax = max(x, rmax);
cmin = min(y, cmin);
cmax = max(y, cmax);
}
rl = rmin; rr = rmax; cl = cmin; cr = cmax;
fact[0] = 1;
for(ll i = 1; i <= 10000000; i++)
{
fact[i] = (fact[i - 1]*i)%MOD;
}
for(ll i = 0; i < 3100; i++)
{
choose[i][0] = 1;
}
for(ll j = 1; j < 3100; j++)
{
for(ll i = 1; i < 3100; i++)
{
if(i < j) choose[i][j] = 0;
else if(i == j) choose[i][j] = 1;
else
{
choose[i][j] = (ll(choose[i - 1][j]) + ll(choose[i - 1][j - 1]))%MOD;
}
}
}
ll tmp = (rmax - rmin + 1)*(cmax - cmin + 1);
tmp -= n;
tmp = fact[tmp];
ll h = rmax - rmin + 1;
ll w = cmax - cmin + 1;
dp[h][w] = tmp;
for(ll i = h; i <= r; i++)
{
for(ll j = w; j <= c; j++)
{
dp[i][j] = (dp[i][j] + (dp[i - 1][j]*fact[j])%MOD + (dp[i][j - 1]*fact[i])%MOD)%MOD;
}
}
ll answer = dp[r][c];
answer = (answer*ll(choose[rmin-1+r-rmax][rmin-1]))%MOD;
answer = (answer*ll(choose[cmin-1+c-cmax][cmin-1]))%MOD;
cout << answer;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
226 ms |
230460 KB |
Output is correct |
| 2 |
Correct |
189 ms |
230460 KB |
Output is correct |
| 3 |
Correct |
196 ms |
230460 KB |
Output is correct |
| 4 |
Correct |
206 ms |
230460 KB |
Output is correct |
| 5 |
Correct |
213 ms |
230460 KB |
Output is correct |
| 6 |
Correct |
193 ms |
230460 KB |
Output is correct |
| 7 |
Correct |
189 ms |
230460 KB |
Output is correct |
| 8 |
Correct |
173 ms |
230460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
230460 KB |
Output is correct |
| 2 |
Correct |
189 ms |
230460 KB |
Output is correct |
| 3 |
Correct |
189 ms |
230460 KB |
Output is correct |
| 4 |
Correct |
219 ms |
230460 KB |
Output is correct |
| 5 |
Correct |
226 ms |
230460 KB |
Output is correct |
| 6 |
Correct |
193 ms |
230460 KB |
Output is correct |
| 7 |
Correct |
196 ms |
230460 KB |
Output is correct |
| 8 |
Correct |
216 ms |
230460 KB |
Output is correct |
| 9 |
Correct |
196 ms |
230460 KB |
Output is correct |
| 10 |
Correct |
176 ms |
230460 KB |
Output is correct |
| 11 |
Correct |
209 ms |
230460 KB |
Output is correct |
| 12 |
Correct |
176 ms |
230460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
203 ms |
230460 KB |
Output is correct |
| 2 |
Correct |
199 ms |
230460 KB |
Output is correct |
| 3 |
Correct |
209 ms |
230460 KB |
Output is correct |
| 4 |
Correct |
239 ms |
230460 KB |
Output is correct |
| 5 |
Correct |
229 ms |
230460 KB |
Output is correct |
| 6 |
Correct |
243 ms |
230460 KB |
Output is correct |
| 7 |
Correct |
179 ms |
230460 KB |
Output is correct |
| 8 |
Correct |
203 ms |
230460 KB |
Output is correct |
| 9 |
Correct |
206 ms |
230460 KB |
Output is correct |
| 10 |
Correct |
296 ms |
230460 KB |
Output is correct |
| 11 |
Correct |
266 ms |
230460 KB |
Output is correct |
| 12 |
Correct |
223 ms |
230460 KB |
Output is correct |
| 13 |
Correct |
223 ms |
230460 KB |
Output is correct |
| 14 |
Correct |
209 ms |
230460 KB |
Output is correct |
| 15 |
Correct |
326 ms |
230460 KB |
Output is correct |
| 16 |
Correct |
309 ms |
230460 KB |
Output is correct |
| 17 |
Correct |
216 ms |
230460 KB |
Output is correct |
| 18 |
Correct |
336 ms |
230460 KB |
Output is correct |
