oj.uz

Submission #17772

# Submission time Handle Problem Language Result Execution time Memory
17772 2016-01-12T10:54:50 Z chrome Energetic turtle (IZhO11_turtle) C++
40 / 100
 268 ms 123896 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define foreach(it, S) for (__typeof (S.begin()) it = S.begin(); it != S.end(); it++)
#define all(x) x.begin(), x.end()
#define endl '\n'
#define _ ios_base :: sync_with_stdio(false); cin.tie(NULL);

#ifdef inputf
	#define fname ""
#else
	#define fname "" // <- Here
#endif

const double eps = 1e-9;
const int MaxN = int(2e5) + 256;
const int MOD = int(1e9) + 7;

template <typename T> inline T gcd(T a, T b) {
	return b ? gcd (b, a % b) : a;
}

inline bool Palindrome(const string& s) {
	return equal(s.begin(), s.end(), s.rbegin());
}

int d[21][1200][1200];
int f[10 * MaxN], inv[10 * MaxN];
int a[1200][1200];
int c[5000][5000];

inline int binpow(int a, int n, int z) {
	int res = 1;
	while (n) {
		if (n & 1)
			res = (res * 1ll * a) % z;
		a = (a * 1ll * a) % z;
		n >>= 1;
	}
	return res;
}

inline int get(int n, int k, int z) {
	return f[n] * inv[k] % z * inv[n - k] % z; 
}

inline bool prime(int v) {
	for (int i = 2; i * i <= v; ++i)
		if (v % i == 0)
			return false;
	return true;
}

int n, m, k, t, z;

int gcd(int a, int b, int & x, int & y) {
	if (a == 0) {
		x = 0; y = 1;
		return b;
	}
	int x1, y1;
	int d = gcd(b%a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

int q(int cnt, int x, int y) {
	if (cnt > t || x > n || y > m)
		return 0;
	if (x == n && y == m)
		return 1;
	int &res = d[cnt][x][y];
	if (~res)
		return res;
	res = 0;
	if (a[x][y])
		++cnt;
	res = (q(cnt, x + 1, y) + q(cnt, x, y + 1)) % z;
	return res;
}

int main() { // _
	#ifdef lcl
		freopen(fname".in", "r", stdin);
		freopen(fname".out", "w", stdout);
	#endif

	scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);

	for (int i = 0; i < k; ++i) {
		int x, y; scanf("%d%d", &x, &y);
		a[x][y] = 1;
	}

	f[0] = inv[0] = 1;
	
	for (int i = 1; i <= n + m; ++i) {
		f[i] = f[i - 1] * 1ll * i % z;
		// inv[i] = binpow(f[i], z - 2, z);
		int x = 0, y = 0;
		int g = gcd(f[i], z, x, y);
		x = (x % z + z) % z;
		inv[i] = x;
	}
	
	if (!k) {
		cout << get(n + m, n, z);
		return 0;
	}

	memset(d, 255, sizeof d);
	cout << q(0, 0, 0);
	
	return 0;
}

Compilation message

turtle.cpp: In function 'int main()':
turtle.cpp:104:7: warning: unused variable 'g' [-Wunused-variable]
   int g = gcd(f[i], z, x, y);
       ^
turtle.cpp:91:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d%d", &n, &m, &k, &t, &z);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
turtle.cpp:94:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 110 ms 118808 KB Output is correct
3 Correct 102 ms 118648 KB Output is correct
4 Correct 104 ms 118700 KB Output is correct
5 Correct 117 ms 118776 KB Output is correct
6 Correct 123 ms 118820 KB Output is correct
7 Correct 130 ms 118904 KB Output is correct
8 Correct 160 ms 118868 KB Output is correct
9 Incorrect 194 ms 119288 KB Output isn't correct
10 Incorrect 153 ms 119264 KB Output isn't correct
11 Runtime error 14 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 253 ms 123788 KB Output isn't correct
13 Runtime error 15 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 259 ms 120836 KB Output isn't correct
15 Runtime error 14 ms 440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 14 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 14 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 15 ms 608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 268 ms 123896 KB Output isn't correct
20 Runtime error 15 ms 664 KB Execution killed with signal 11 (could be triggered by violating memory limits)