Submission #17771

# Submission time Handle Problem Language Result Execution time Memory
17771 2016-01-12T10:51:32 Z chrome Energetic turtle (IZhO11_turtle) C++
40 / 100
696 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 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);
	}
	
	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:79: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:82: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);
             ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 124 ms 118684 KB Output is correct
3 Correct 102 ms 118648 KB Output is correct
4 Correct 106 ms 118748 KB Output is correct
5 Correct 105 ms 118780 KB Output is correct
6 Correct 136 ms 118780 KB Output is correct
7 Correct 132 ms 119032 KB Output is correct
8 Correct 162 ms 118904 KB Output is correct
9 Incorrect 196 ms 119160 KB Output isn't correct
10 Incorrect 161 ms 119204 KB Output isn't correct
11 Runtime error 13 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 468 ms 123816 KB Output isn't correct
13 Runtime error 15 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Incorrect 407 ms 120836 KB Output isn't correct
15 Runtime error 14 ms 504 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 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 15 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Incorrect 696 ms 123896 KB Output isn't correct
20 Runtime error 16 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)