| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 736240 |
2023-05-05T10:58:16 Z |
vjudge1 |
Boat (APIO16_boat) |
C++17 |
|
6 ms |
7124 KB |
#include <bits/stdc++.h>
using namespace std;
int f[1000][501];
int a[500], b[500], cnt[1000];
int fact[501], ifact[501];
const int MOD = 1e9 + 7;
int lC[1000][501];
int C[501][501];
int g[501][1000];
inline int Power(int a, int b) {
int64_t res = 1;
for (; b; b >>= 1, a = 1ll * a * a % MOD) {
if (b & 1) (res *= a) %= MOD;
}
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
/// small nCk
for (int i = 0; i <= n; i++) C[i][0] = C[i][i] = 1;
for (int i = 0; i <= n; i++) {
for (int j = 1; j < i; j++) {
C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
if (C[i][j] >= MOD) C[i][j] -= MOD;
}
}
/// calc ifact
fact[0] = 1;
for (int i = 1; i <= n; i++) fact[i] = 1ll * fact[i - 1] * i % MOD;
ifact[n] = Power(fact[n], MOD - 2);
for (int i = n; i >= 1; i--) ifact[i - 1] = 1ll * ifact[i] * i % MOD;
/// input
for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
vector<int> point;
point.reserve(n * 2);
for (int i = 0; i < n; i++) point.emplace_back(a[i]);
for (int i = 0; i < n; i++) point.emplace_back(b[i] + 1);
sort(point.begin(), point.end());
point.resize(unique(point.begin(), point.end()) - point.begin());
assert(point.size() <= n * 2);
int m = point.size() - 1;
vector<int> range(m);
for (int i = 0; i < m; i++) range[i] = point[i + 1] - point[i];
for (int i = 0; i < n; i++) a[i] = lower_bound(point.begin(), point.end(), a[i]) - point.begin();
for (int i = 0; i < n; i++) b[i] = lower_bound(point.begin(), point.end(), b[i] + 1) - point.begin();
for (int i = 0; i < n; i++) {
cnt[a[i]]++;
cnt[b[i]]--;
}
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
/// large nCk
for (int i = 0; i < m; i++) {
lC[i][0] = 1;
for (int j = 1, k = range[i]; j <= cnt[i]; j++, k--) lC[i][j] = 1ll * lC[i][j - 1] * k % MOD;
for (int j = 1; j <= cnt[i]; j++) lC[i][j] = 1ll * lC[i][j] * ifact[j] % MOD;
}
/// calc f
for (int i = 0; i < m; i++) {
for (int j = 1; j <= cnt[i] && j <= range[i]; j++) {
for (int k = 1; k <= j; k++) {
f[i][j] += 1ll * lC[i][j] * C[cnt[i] - 1][k - 1] % MOD;
if (f[i][j] >= MOD) f[i][j] -= MOD;
}
}
}
for (int i = 0; i < m; i++) g[0][i] = 1;
for (int i = 0; i < n; i++) {
for (int j = a[i]; j < b[i]; j++) {
for (int k = i, z = 0; k >= 0; k--) {
z += a[k] <= j && j < b[k];
if (z > range[j]) z--;
int x = j ? g[k][j - 1] : 1;
if (x != 0) {
g[i + 1][j] += 1ll * x * f[j][z] % MOD;
if (g[i + 1][j] >= MOD) g[i + 1][j] -= MOD;
}
}
}
for (int j = a[i] + 1; j < m; j++) {
g[i + 1][j] += g[i + 1][j - 1];
if (g[i + 1][j] >= MOD) g[i + 1][j] -= MOD;
}
}
int res = 0;
for (int i = 1; i <= n; i++) {
res += g[i][m - 1];
if (res >= MOD) res -= MOD;
}
cout << res;
}
Compilation message
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from boat.cpp:1:
boat.cpp: In function 'int main()':
boat.cpp:46:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
46 | assert(point.size() <= n * 2);
| ~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
