oj.uz

Submission #248784

# Submission time Handle Problem Language Result Execution time Memory
248784 2020-07-13T11:44:14 Z srvlt Energetic turtle (IZhO11_turtle) C++14
40 / 100
 52 ms 28544 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

constexpr int n0 = 2003, k0 = 23;
int n, m, k, t, z, C[n0][n0], f[k0], cf[k0];
array <int, 2> p[k0];

int w(int x, int y, int x2, int y2) {
	if (x2 - x + y2 - y >= n0) assert(false);
	return C[x2 - x + y2 - y][x2 - x];
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	#ifdef LOCAL
		freopen("input.txt", "r", stdin);
	#endif
	
	cin >> n >> m >> k >> t >> z;
	C[0][0] = 1 % z;
	for (int i = 1; i < n0; i++) {
		C[i][0] = 1 % z;
		for (int j = 1; j <= i; j++) {
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % z;
		}
	}
	for (int i = 0; i < k; i++)
		cin >> p[i][0] >> p[i][1];
	sort(p, p + k);
	for (int mask = 1; mask < (1 << k); mask++) {
		int bad = 0, res = 1 % z, last = -1;
		int b = __builtin_popcount(mask);
		for (int i = 0; i < k; i++) {
			if (mask >> i & 1) {
				if (last != -1 && p[i][1] < p[last][1]) {
					bad = 1;
					break;
				}
				if (last == -1) res = (ll)res * w(0, 0, p[i][0], p[i][1]) % z;
				else res = (ll)res * w(p[last][0], p[last][1], p[i][0], p[i][1]) % z;
				last = i;
			}
		}
		if (bad) continue;
		res = (ll)res * w(p[last][0], p[last][1], n, m) % z;
		f[b] = (f[b] + res) % z;
	}
	int res = w(0, 0, n, m);
	for (int i = t + 1; i <= k; i++) {
		int cur = 0;
		for (int j = t + 1; j < i; j++)
			cur = (cur + (ll)C[i][j] * cf[j] % z) % z;
		cf[i] = (z - 1) - cur;
		res = (res + (ll)cf[i] * f[i] % z) % z;
	}
	cout << res;
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14208 KB Output is correct
2 Correct 17 ms 14208 KB Output is correct
3 Correct 17 ms 14208 KB Output is correct
4 Correct 22 ms 14200 KB Output is correct
5 Correct 39 ms 14208 KB Output is correct
6 Correct 18 ms 14208 KB Output is correct
7 Correct 18 ms 14208 KB Output is correct
8 Correct 18 ms 14208 KB Output is correct
9 Runtime error 52 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 44 ms 28540 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 37 ms 28488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 37 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 37 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 37 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 38 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 36 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 40 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 37 ms 28544 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 39 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 40 ms 28536 KB Execution killed with signal 11 (could be triggered by violating memory limits)