oj.uz

Submission #102342

# Submission time Handle Problem Language Result Execution time Memory
102342 2019-03-24T11:43:01 Z jwvg0425 마스코트 (JOI13_mascots) C++17
10 / 100
 70 ms 72292 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[55][55][55][55];
int r, c, n;
i64 facto[9000005];

i64 solve(int lx, int ly, int rx, int ry)
{
	if (table[lx][ly][rx][ry] != -1)
		return table[lx][ly][rx][ry];

	auto& res = table[lx][ly][rx][ry];
	res = 0;

	i64 l = 0, r = 0, u = 0, d = 0;

	if (lx > 1)
		l = (facto[ry - ly + 1] * solve(lx - 1, ly, rx, ry)) % MOD;

	if (rx < r)
		r = (facto[ry - ly + 1] * solve(lx, ly, rx + 1, ry)) % MOD;

	if (ly > 1)
		u = (facto[rx - lx + 1] * solve(lx, ly - 1, rx, ry)) % MOD;

	if (ry < c)
		d = (facto[rx - lx + 1] * solve(lx, ly, rx, ry + 1)) % MOD;

	res = l + r + u + d;

	if (res == 0)
		res = 1;

	return res;
}

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

	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 count = (rx - lx + 1)* (ry - ly + 1) - n;

	printf("%lld\n", (facto[count] * solve(lx, ly, rx, ry)) % MOD);

	return 0;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:69: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:81: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 56 ms 72056 KB Output is correct
2 Correct 63 ms 71928 KB Output is correct
3 Correct 59 ms 72056 KB Output is correct
4 Correct 59 ms 71928 KB Output is correct
5 Correct 70 ms 71928 KB Output is correct
6 Correct 67 ms 71916 KB Output is correct
7 Correct 58 ms 71928 KB Output is correct
8 Correct 62 ms 71928 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 71928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 72292 KB Output isn't correct
2 Halted 0 ms 0 KB -