답안 #47634 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47634	2018-05-06T06:42:29 Z	E869120	Boat (APIO16_boat)	C++14	36 / 100	2000 ms	10624 KB

boat

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #47634

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 0 / 22.0

Subtask #3 27.0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
0 / 22.0

Subtask #3
27.0 / 27.0

Subtask #4
0 / 42.0