oj.uz

Submission #736244

# Submission time Handle Problem Language Result Execution time Memory
736244 2023-05-05T11:03:52 Z vjudge1 Boat (APIO16_boat) C++17
9 / 100
 183 ms 7176 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] : (k == 0);
                                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);
      |                ~~~~~~~~~~~~~^~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7124 KB Output is correct
2 Correct 7 ms 7124 KB Output is correct
3 Correct 6 ms 7176 KB Output is correct
4 Correct 6 ms 7152 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 6 ms 7164 KB Output is correct
8 Correct 6 ms 7124 KB Output is correct
9 Correct 7 ms 7148 KB Output is correct
10 Correct 6 ms 7124 KB Output is correct
11 Correct 6 ms 7124 KB Output is correct
12 Correct 6 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 6 ms 7124 KB Output is correct
15 Correct 6 ms 7120 KB Output is correct
16 Correct 4 ms 3916 KB Output is correct
17 Correct 4 ms 4052 KB Output is correct
18 Correct 4 ms 3924 KB Output is correct
19 Correct 7 ms 3924 KB Output is correct
20 Correct 4 ms 3924 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7124 KB Output is correct
2 Correct 7 ms 7124 KB Output is correct
3 Correct 6 ms 7176 KB Output is correct
4 Correct 6 ms 7152 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 6 ms 7164 KB Output is correct
8 Correct 6 ms 7124 KB Output is correct
9 Correct 7 ms 7148 KB Output is correct
10 Correct 6 ms 7124 KB Output is correct
11 Correct 6 ms 7124 KB Output is correct
12 Correct 6 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 6 ms 7124 KB Output is correct
15 Correct 6 ms 7120 KB Output is correct
16 Correct 4 ms 3916 KB Output is correct
17 Correct 4 ms 4052 KB Output is correct
18 Correct 4 ms 3924 KB Output is correct
19 Correct 7 ms 3924 KB Output is correct
20 Correct 4 ms 3924 KB Output is correct
21 Incorrect 183 ms 6796 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7124 KB Output is correct
2 Correct 7 ms 7124 KB Output is correct
3 Correct 6 ms 7176 KB Output is correct
4 Correct 6 ms 7152 KB Output is correct
5 Correct 6 ms 7124 KB Output is correct
6 Correct 6 ms 7124 KB Output is correct
7 Correct 6 ms 7164 KB Output is correct
8 Correct 6 ms 7124 KB Output is correct
9 Correct 7 ms 7148 KB Output is correct
10 Correct 6 ms 7124 KB Output is correct
11 Correct 6 ms 7124 KB Output is correct
12 Correct 6 ms 7124 KB Output is correct
13 Correct 6 ms 7124 KB Output is correct
14 Correct 6 ms 7124 KB Output is correct
15 Correct 6 ms 7120 KB Output is correct
16 Correct 4 ms 3916 KB Output is correct
17 Correct 4 ms 4052 KB Output is correct
18 Correct 4 ms 3924 KB Output is correct
19 Correct 7 ms 3924 KB Output is correct
20 Correct 4 ms 3924 KB Output is correct
21 Incorrect 183 ms 6796 KB Output isn't correct
22 Halted 0 ms 0 KB -