oj.uz

Submission #87083

# Submission time Handle Problem Language Result Execution time Memory
87083 2018-11-29T12:11:58 Z Just_Solve_The_Problem Energetic turtle (IZhO11_turtle) C++11
70 / 100
 897 ms 8480 KB 
#include <bits/stdc++.h>

#define ll long long

using namespace std;

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

int mod;
int cnt[N], lp[N];
map < pair < int, int >, int > mp;

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) {
	if (mp.count({n, k})) {
		return mp[{n, k}];
	} else if (k > n) {
		return 0;
	}
	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;
	return mp[{n, k}] = res;
}

int n, m, k, t;
int dp[33][33];
int dist[33][33];
int dist1[33][33];
pair < int, int > ar[33];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(dp, -1, sizeof dp);
	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++;
	}
	k++;
	ar[k] = {n, m};
	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);
	}
	int ans = 0;
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j < i; j++) {
			// ar[i].first <= ar[j].first
			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 len1 = abs(ar[i].first - ar[j].first);
			int len2 = abs(ar[i].second - ar[j].second);
			dist[i][j] = dist[j][i] = calc(len1 + len2, len1);
			dist1[i][j] = dist1[j][i] = dist[i][j];
		}
	}
	for (int i = 1; i <= k; i++) {
		for (int j = 1; j < i; j++) {
			for (int l = j + 1; l < i; l++) {
				if (ar[j].second <= ar[l].second && ar[l].second <= ar[i].second) {
					dist1[i][j] = dist1[j][i] = add(dist1[i][j], mod - mult(dist1[i][l], dist1[l][j]));
				}
			}
		}
	}
	for (int i = 2; i <= t + 1; i++) {
		for (int j = 1; j <= k; j++) {
			dp[i][j] = dp[1][j];
			for (int l = 1; l < j; l++) {
				if (ar[l].second <= ar[j].second) {
					if (dp[i - 1][l] == -1) continue;
					dp[i][j] = add(dp[i][j], mult(dp[i - 1][l], dist1[j][l]));
				}
			}
		}
	}
	cout << dp[t + 1][k] << endl;
}
/*
5 5 3 0 1000000000
2 2
2 3
3 3

5 5 1 0 1000000
4 5
*/

Compilation message

turtle.cpp:71:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
turtle.cpp: In function 'int main()':
turtle.cpp:90:6: warning: unused variable 'ans' [-Wunused-variable]
  int ans = 0;
      ^~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2296 KB Output is correct
2 Correct 8 ms 2296 KB Output is correct
3 Correct 9 ms 2296 KB Output is correct
4 Correct 9 ms 2296 KB Output is correct
5 Correct 10 ms 2268 KB Output is correct
6 Correct 11 ms 2296 KB Output is correct
7 Correct 14 ms 2400 KB Output is correct
8 Correct 13 ms 2268 KB Output is correct
9 Correct 62 ms 2296 KB Output is correct
10 Correct 158 ms 2424 KB Output is correct
11 Correct 678 ms 3192 KB Output is correct
12 Runtime error 107 ms 8440 KB Execution killed with signal 8 (could be triggered by violating memory limits)
13 Correct 845 ms 4420 KB Output is correct
14 Correct 680 ms 3192 KB Output is correct
15 Correct 897 ms 3152 KB Output is correct
16 Runtime error 123 ms 8480 KB Execution killed with signal 8 (could be triggered by violating memory limits)
17 Runtime error 115 ms 8472 KB Execution killed with signal 8 (could be triggered by violating memory limits)
18 Runtime error 114 ms 8372 KB Execution killed with signal 8 (could be triggered by violating memory limits)
19 Runtime error 117 ms 8432 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Runtime error 111 ms 8476 KB Execution killed with signal 8 (could be triggered by violating memory limits)