oj.uz

Submission #102452

# Submission time Handle Problem Language Result Execution time Memory
102452 2019-03-25T04:44:57 Z jwvg0425 마스코트 (JOI13_mascots) C++17
100 / 100
 468 ms 213520 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <iterator>
#include <chrono>
#define MOD 1000000007
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second

using namespace std;

using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using vi = vector<long long int>;

i64 table[3005][3005];
i64 ctable[3005][3005];
int r, c, n;
i64 facto[9000005];

i64 solve(int w, int h)
{
	if (w > r || h > c)
		return 0;

	if (w == r && h == c)
		return 1;

	if (table[w][h] != -1)
		return table[w][h];

	auto& res = table[w][h];
	i64 lr = (facto[h] * solve(w + 1, h)) % MOD;
	i64 ud = (facto[w] * solve(w, h + 1)) % MOD;

	res = (lr + ud) % MOD;

	return res;
}

i64 comb(int n, int k)
{
	if (k == 0 || k == n)
		return 1;

	if (ctable[n][k] != -1)
		return ctable[n][k];

	auto& res = ctable[n][k];

	res = (comb(n - 1, k - 1) + comb(n - 1, k)) % MOD;

	return res;
}

int main()
{
	memset(table, -1, sizeof(table));
	memset(ctable, -1, sizeof(ctable));

	scanf("%d %d %d", &r, &c, &n);

	int lx = r, rx = 0, ly = c, ry = 0;

	facto[0] = 1;

	for (int i = 1; i <= r * c; i++)
		facto[i] = (facto[i - 1] * i) % MOD;

	for (int i = 0; i < n; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		lx = min(lx, x);
		rx = max(rx, x);
		ly = min(ly, y);
		ry = max(ry, y);
	}
	int w = rx - lx + 1;
	int h = ry - ly + 1;
	int count = w * h - n;
	i64 ans = (facto[count] * solve(w, h)) % MOD;

	// 좌,우 / 상, 하 고르는 경우 끼워넣는다
	ans = (ans * comb(r - w, r - rx)) % MOD;
	ans = (ans * comb(c - h, c - ry)) % MOD;

	printf("%lld\n", ans);

	return 0;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &r, &c, &n);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 141624 KB Output is correct
2 Correct 126 ms 141688 KB Output is correct
3 Correct 116 ms 141688 KB Output is correct
4 Correct 113 ms 141660 KB Output is correct
5 Correct 111 ms 141688 KB Output is correct
6 Correct 114 ms 141700 KB Output is correct
7 Correct 118 ms 141648 KB Output is correct
8 Correct 117 ms 141728 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 141688 KB Output is correct
2 Correct 127 ms 141716 KB Output is correct
3 Correct 131 ms 141680 KB Output is correct
4 Correct 139 ms 141668 KB Output is correct
5 Correct 126 ms 141692 KB Output is correct
6 Correct 127 ms 141736 KB Output is correct
7 Correct 119 ms 141688 KB Output is correct
8 Correct 124 ms 141688 KB Output is correct
9 Correct 129 ms 141788 KB Output is correct
10 Correct 130 ms 141672 KB Output is correct
11 Correct 115 ms 141688 KB Output is correct
12 Correct 121 ms 141672 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 142160 KB Output is correct
2 Correct 133 ms 142428 KB Output is correct
3 Correct 122 ms 142456 KB Output is correct
4 Correct 161 ms 148060 KB Output is correct
5 Correct 138 ms 148216 KB Output is correct
6 Correct 154 ms 150392 KB Output is correct
7 Correct 142 ms 155288 KB Output is correct
8 Correct 190 ms 173216 KB Output is correct
9 Correct 248 ms 212728 KB Output is correct
10 Correct 382 ms 201080 KB Output is correct
11 Correct 282 ms 200568 KB Output is correct
12 Correct 236 ms 204664 KB Output is correct
13 Correct 139 ms 146808 KB Output is correct
14 Correct 228 ms 212216 KB Output is correct
15 Correct 468 ms 213368 KB Output is correct
16 Correct 322 ms 189560 KB Output is correct
17 Correct 217 ms 212728 KB Output is correct
18 Correct 425 ms 213520 KB Output is correct