oj.uz

Submission #87067

# Submission time Handle Problem Language Result Execution time Memory
87067 2018-11-29T11:03:22 Z Just_Solve_The_Problem Energetic turtle (IZhO11_turtle) C++11
5 / 100
 733 ms 5368 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)3e5 + 7;

int mod;
int cnt[N], lp[N];

int mult(int a, int b) {
	return (a * 1LL * b) % mod;
}

int add(int a, int b) {
	return (a + b) % mod;
}

void precalc() {
	for (int i = 2; i < N; i++) {
		if (lp[i]) continue;
		for (int j = i; j < N; j += i) {
			if (!lp[j]) {
				lp[j] = i;
			}
		}
 	}
}

void add1(int x, int val) {
	while (x > 1) {
		cnt[lp[x]] += val;
		x /= lp[x];
	}
}

int calc(int n, int k) {
	int res = 1;
	for (int i = 2; i <= n; i++) {
		add1(i, 1);
	}
	for (int i = 2; i <= k; i++) {
		add1(i, -1);
	}
	for (int i = 2; i <= n - k; i++) {
		add1(i, -1);
	}
	for (int i = 2; i <= n; i++) {
		while (cnt[i] > 0) {
			res = mult(res, i);
			cnt[i]--;
		}
	}
	return res;
}

int n, m, k, t;
int dp[22][22];
pair < int, int > ar[22];

main() {
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	//cout.tie(0);
	precalc();
	cin >> n >> m >> k >> t >> mod;
	n++; m++;
	for (int i = 1; i <= k; i++) {
		cin >> ar[i].first >> ar[i].second;
		ar[i].first++;
		ar[i].second++;
	}
	sort(ar + 1, ar + k + 1);
	for (int i = 1; i <= k; i++) {
		dp[1][i] = calc(ar[i].first + ar[i].second - 2, ar[i].first - 1);
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j < i; j++) {
			if (ar[j].second <= ar[i].second) {
				dp[1][i] = add(dp[1][i], mod - mult(dp[1][j], calc(abs(ar[j].second - ar[i].second) + abs(ar[i].first - ar[j].first), abs(ar[i].first - ar[j].first))));
			}
		}
	}
	int ans = calc(n + m - 2, n - 1);
	for (int i = 1; i <= k; i++) {
		ans = add(ans, mod - mult(calc(n - ar[i].first + m - ar[i].second, n - ar[i].first), dp[1][i]));
	}
	cout << ans << endl;
}
/*
5 5 3 4 1000000000
2 2
2 3
3 3
*/

Compilation message

turtle.cpp:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Incorrect 3 ms 1528 KB Output isn't correct
3 Incorrect 6 ms 1528 KB Output isn't correct
4 Incorrect 6 ms 1528 KB Output isn't correct
5 Incorrect 7 ms 1528 KB Output isn't correct
6 Incorrect 8 ms 1528 KB Output isn't correct
7 Incorrect 6 ms 1528 KB Output isn't correct
8 Incorrect 9 ms 1528 KB Output isn't correct
9 Incorrect 43 ms 1572 KB Output isn't correct
10 Incorrect 76 ms 1660 KB Output isn't correct
11 Incorrect 513 ms 2312 KB Output isn't correct
12 Runtime error 279 ms 5368 KB Execution killed with signal 8 (could be triggered by violating memory limits)
13 Runtime error 119 ms 5240 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Incorrect 678 ms 2300 KB Output isn't correct
15 Incorrect 733 ms 2296 KB Output isn't correct
16 Runtime error 313 ms 5112 KB Execution killed with signal 8 (could be triggered by violating memory limits)
17 Runtime error 284 ms 5272 KB Execution killed with signal 8 (could be triggered by violating memory limits)
18 Runtime error 602 ms 5368 KB Execution killed with signal 8 (could be triggered by violating memory limits)
19 Runtime error 470 ms 5320 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Runtime error 232 ms 5156 KB Execution killed with signal 8 (could be triggered by violating memory limits)