oj.uz

Submission #87081

# Submission time Handle Problem Language Result Execution time Memory
87081 2018-11-29T12:05:20 Z Just_Solve_The_Problem Energetic turtle (IZhO11_turtle) C++11
65 / 100
 886 ms 5288 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];
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}];
	}
	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 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
*/

Compilation message

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

Subtask #1
65.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 6 ms 1528 KB Output is correct
3 Correct 6 ms 1532 KB Output is correct
4 Correct 6 ms 1528 KB Output is correct
5 Correct 7 ms 1528 KB Output is correct
6 Correct 8 ms 1532 KB Output is correct
7 Correct 11 ms 1528 KB Output is correct
8 Correct 10 ms 1528 KB Output is correct
9 Correct 59 ms 1696 KB Output is correct
10 Correct 152 ms 1636 KB Output is correct
11 Correct 627 ms 2464 KB Output is correct
12 Runtime error 86 ms 5212 KB Execution killed with signal 8 (could be triggered by violating memory limits)
13 Runtime error 65 ms 5116 KB Execution killed with signal 8 (could be triggered by violating memory limits)
14 Correct 672 ms 2464 KB Output is correct
15 Correct 886 ms 2336 KB Output is correct
16 Runtime error 102 ms 5188 KB Execution killed with signal 8 (could be triggered by violating memory limits)
17 Runtime error 96 ms 5196 KB Execution killed with signal 8 (could be triggered by violating memory limits)
18 Runtime error 95 ms 5152 KB Execution killed with signal 8 (could be triggered by violating memory limits)
19 Runtime error 167 ms 5192 KB Execution killed with signal 8 (could be triggered by violating memory limits)
20 Runtime error 98 ms 5288 KB Execution killed with signal 8 (could be triggered by violating memory limits)