oj.uz

Submission #47634

# Submission time Handle Problem Language Result Execution time Memory
47634 2018-05-06T06:42:29 Z E869120 Boat (APIO16_boat) C++14
36 / 100
 2000 ms 10624 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, A[509], B[509], nr1[509][509], nr2[1009][509], dp[1009][509], inv[1009], mod = 1000000007; vector<long long>V;

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 60; i++) {
		if ((b / (1LL << i)) % 2 == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}
long long Div(long long a, long long b, long long m) {
	return (a*modpow(b, m - 2, m)) % m;
}

void init() {
	for (int i = 0; i <= 500; i++) {
		for (int j = 0; j <= 500; j++) {
			if (i == 0 || j == 0) nr1[i][j] = 1;
			else nr1[i][j] = (nr1[i - 1][j] + nr1[i][j - 1]) % mod;
		}
	}
	for (int i = 1; i <= 1000; i++) inv[i] = Div(1, i, mod);
	for (int i = 0; i < V.size() - 1; i++) {
		long long L = V[i + 1] - V[i], S = 1;
		for (int j = 0; j <= 500; j++) {
			if (L < j) break;
			nr2[i][j] = S;
			S *= (L - j); S %= mod;
			S *= inv[j + 1]; S %= mod;
		}
	}
}
long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return nr1[n - r][r];
}
long long solve(long long v, long long pos) {
	long long res = 0;
	for (int i = 1; i <= v; i++) {
		res += ncr(v - 1, i - 1)*nr2[pos][i];
		res %= mod;
	}
	return res;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i]; B[i]++;
		V.push_back(A[i]);
		V.push_back(B[i]);
	}
	sort(V.begin(), V.end());
	V.erase(unique(V.begin(), V.end()), V.end());
	for (int i = 1; i <= N; i++) {
		A[i] = lower_bound(V.begin(), V.end(), A[i]) - V.begin();
		B[i] = lower_bound(V.begin(), V.end(), B[i]) - V.begin();
	}
	init();
	dp[0][1] = 1;
	for (int i = 0; i < V.size() - 1; i++) {
		for (int j = 1; j <= N + 1; j++) {
			if (dp[i][j] == 0) continue;
			dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod;
			int G = 0;
			for (int k = j + 1; k <= N + 1; k++) {
				if (A[k - 1] <= i && i < B[k - 1]) {
					G++;
					dp[i + 1][k] += dp[i][j] * solve(G, i);
					dp[i + 1][k] %= mod;
				}
			}
		}
	}
	long long sum = 0;
	for (int i = 2; i <= N + 1; i++) sum += dp[V.size() - 1][i];
	cout << sum%mod << endl;
	return 0;
}

Compilation message

boat.cpp: In function 'void init()':
boat.cpp:28:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size() - 1; i++) {
                  ~~^~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 10360 KB Output is correct
2 Correct 183 ms 10360 KB Output is correct
3 Correct 179 ms 10360 KB Output is correct
4 Correct 179 ms 10392 KB Output is correct
5 Correct 184 ms 10392 KB Output is correct
6 Correct 100 ms 10460 KB Output is correct
7 Correct 99 ms 10496 KB Output is correct
8 Correct 103 ms 10576 KB Output is correct
9 Correct 103 ms 10596 KB Output is correct
10 Correct 103 ms 10596 KB Output is correct
11 Correct 102 ms 10596 KB Output is correct
12 Correct 106 ms 10596 KB Output is correct
13 Correct 103 ms 10604 KB Output is correct
14 Correct 98 ms 10620 KB Output is correct
15 Correct 99 ms 10624 KB Output is correct
16 Correct 44 ms 10624 KB Output is correct
17 Correct 45 ms 10624 KB Output is correct
18 Correct 44 ms 10624 KB Output is correct
19 Correct 44 ms 10624 KB Output is correct
20 Correct 44 ms 10624 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 10360 KB Output is correct
2 Correct 183 ms 10360 KB Output is correct
3 Correct 179 ms 10360 KB Output is correct
4 Correct 179 ms 10392 KB Output is correct
5 Correct 184 ms 10392 KB Output is correct
6 Correct 100 ms 10460 KB Output is correct
7 Correct 99 ms 10496 KB Output is correct
8 Correct 103 ms 10576 KB Output is correct
9 Correct 103 ms 10596 KB Output is correct
10 Correct 103 ms 10596 KB Output is correct
11 Correct 102 ms 10596 KB Output is correct
12 Correct 106 ms 10596 KB Output is correct
13 Correct 103 ms 10604 KB Output is correct
14 Correct 98 ms 10620 KB Output is correct
15 Correct 99 ms 10624 KB Output is correct
16 Correct 44 ms 10624 KB Output is correct
17 Correct 45 ms 10624 KB Output is correct
18 Correct 44 ms 10624 KB Output is correct
19 Correct 44 ms 10624 KB Output is correct
20 Correct 44 ms 10624 KB Output is correct
21 Execution timed out 2045 ms 10624 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 10624 KB Output is correct
2 Correct 59 ms 10624 KB Output is correct
3 Correct 77 ms 10624 KB Output is correct
4 Correct 82 ms 10624 KB Output is correct
5 Correct 94 ms 10624 KB Output is correct
6 Correct 253 ms 10624 KB Output is correct
7 Correct 250 ms 10624 KB Output is correct
8 Correct 246 ms 10624 KB Output is correct
9 Correct 254 ms 10624 KB Output is correct
10 Correct 262 ms 10624 KB Output is correct
11 Correct 110 ms 10624 KB Output is correct
12 Correct 75 ms 10624 KB Output is correct
13 Correct 87 ms 10624 KB Output is correct
14 Correct 87 ms 10624 KB Output is correct
15 Correct 106 ms 10624 KB Output is correct
16 Correct 59 ms 10624 KB Output is correct
17 Correct 47 ms 10624 KB Output is correct
18 Correct 56 ms 10624 KB Output is correct
19 Correct 45 ms 10624 KB Output is correct
20 Correct 63 ms 10624 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 10360 KB Output is correct
2 Correct 183 ms 10360 KB Output is correct
3 Correct 179 ms 10360 KB Output is correct
4 Correct 179 ms 10392 KB Output is correct
5 Correct 184 ms 10392 KB Output is correct
6 Correct 100 ms 10460 KB Output is correct
7 Correct 99 ms 10496 KB Output is correct
8 Correct 103 ms 10576 KB Output is correct
9 Correct 103 ms 10596 KB Output is correct
10 Correct 103 ms 10596 KB Output is correct
11 Correct 102 ms 10596 KB Output is correct
12 Correct 106 ms 10596 KB Output is correct
13 Correct 103 ms 10604 KB Output is correct
14 Correct 98 ms 10620 KB Output is correct
15 Correct 99 ms 10624 KB Output is correct
16 Correct 44 ms 10624 KB Output is correct
17 Correct 45 ms 10624 KB Output is correct
18 Correct 44 ms 10624 KB Output is correct
19 Correct 44 ms 10624 KB Output is correct
20 Correct 44 ms 10624 KB Output is correct
21 Execution timed out 2045 ms 10624 KB Time limit exceeded
22 Halted 0 ms 0 KB -