oj.uz

Submission #499767

# Submission time Handle Problem Language Result Execution time Memory
499767 2021-12-29T12:14:35 Z Stickfish Boat (APIO16_boat) C++17
9 / 100
 1695 ms 16400 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const ll MOD = 1000000007;
const int MAXN = 502;

ll fact[MAXN * 2];
ll rfact[MAXN * 2];

ll pw(ll a, ll m) {
    if (!m)
        return 1;
    a %= MOD;
    if (m % 2)
        return (a * pw(a, m - 1)) % MOD;
    return pw(a * a, m / 2);
}

ll choose(ll n, ll k) {
    return (((fact[n] * rfact[k]) % MOD) * rfact[n - k]) % MOD;
}

ll dp[MAXN * 2][MAXN];
ll ndp[MAXN * 2][MAXN];

ll a[MAXN];
ll b[MAXN];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    rfact[0] = fact[0] = 1;
    for (int i = 1; i < 2 * MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
        rfact[i] = pw(fact[i], MOD - 2);
    }
    int n;
    cin >> n;
    vector<ll> cpr = {0};
    vector<ll> sz;
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
        ++b[i];
        cpr.push_back(a[i]);
        cpr.push_back(b[i]);
    }
    sort(cpr.begin(), cpr.end());
    cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin());
    int m = cpr.size();
    for (int i = 0; i + 1 < m; ++i) {
        sz.push_back(cpr[i + 1] - cpr[i]);
        //printf("%Ld ", sz[i]);
    }
    //printf("\n");
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin();
        b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin();
    }
    for (int i = 0; i < m; ++i)
        dp[i][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k <= n; ++k)
                ndp[j][k] = 0;
        }
        for (int j = b[i] - 1; j >= a[i]; --j) {
            for (int k = 0; k <= n; ++k) {
                ndp[j][k] += dp[j][k - 1];
                ndp[j][k] %= MOD;
                //cout << "(" << j << ' ' << k << ": " << ndp[j][k] << ' ' << choose(sz[j], k) << ") ";
                ndp[j + 1][0] += (ndp[j][k] * choose(sz[j], k)) % MOD;
                ndp[j + 1][0] %= MOD;
            }
        }
        for (int j = 1; j < m; ++j) {
            ndp[j][0] += ndp[j - 1][0];
            ndp[j][0] %= MOD;
        }
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k <= n; ++k) {
                ndp[j][k] += dp[j][k];
                ndp[j][k] %= MOD;
            }
        }
        for (int j = 0; j < m; ++j) {
            for (int k = 0; k <= n; ++k)
                dp[j][k] = ndp[j][k];
        }
        //printf("---\n");
        //for (int j = 0; j < m; ++j) {
            //for (int k = 0; k <= n; ++k)
                //printf("%Ld ", dp[j][k]);
            //printf("\n");
        //}
    }
    cout << dp[m - 1][0] - 1 << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 8216 KB Output is correct
2 Correct 717 ms 8228 KB Output is correct
3 Correct 737 ms 8224 KB Output is correct
4 Correct 738 ms 8228 KB Output is correct
5 Correct 762 ms 8224 KB Output is correct
6 Correct 735 ms 8228 KB Output is correct
7 Correct 789 ms 8236 KB Output is correct
8 Correct 754 ms 8260 KB Output is correct
9 Correct 813 ms 8228 KB Output is correct
10 Correct 732 ms 8228 KB Output is correct
11 Correct 726 ms 8220 KB Output is correct
12 Correct 774 ms 8228 KB Output is correct
13 Correct 755 ms 8228 KB Output is correct
14 Correct 749 ms 8228 KB Output is correct
15 Correct 715 ms 8228 KB Output is correct
16 Correct 112 ms 1756 KB Output is correct
17 Correct 100 ms 1876 KB Output is correct
18 Correct 97 ms 1800 KB Output is correct
19 Correct 104 ms 1864 KB Output is correct
20 Correct 110 ms 1740 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 8216 KB Output is correct
2 Correct 717 ms 8228 KB Output is correct
3 Correct 737 ms 8224 KB Output is correct
4 Correct 738 ms 8228 KB Output is correct
5 Correct 762 ms 8224 KB Output is correct
6 Correct 735 ms 8228 KB Output is correct
7 Correct 789 ms 8236 KB Output is correct
8 Correct 754 ms 8260 KB Output is correct
9 Correct 813 ms 8228 KB Output is correct
10 Correct 732 ms 8228 KB Output is correct
11 Correct 726 ms 8220 KB Output is correct
12 Correct 774 ms 8228 KB Output is correct
13 Correct 755 ms 8228 KB Output is correct
14 Correct 749 ms 8228 KB Output is correct
15 Correct 715 ms 8228 KB Output is correct
16 Correct 112 ms 1756 KB Output is correct
17 Correct 100 ms 1876 KB Output is correct
18 Correct 97 ms 1800 KB Output is correct
19 Correct 104 ms 1864 KB Output is correct
20 Correct 110 ms 1740 KB Output is correct
21 Correct 1348 ms 7532 KB Output is correct
22 Correct 1571 ms 7628 KB Output is correct
23 Correct 1566 ms 7500 KB Output is correct
24 Correct 1607 ms 7440 KB Output is correct
25 Correct 1458 ms 7468 KB Output is correct
26 Correct 1695 ms 7284 KB Output is correct
27 Correct 1632 ms 7392 KB Output is correct
28 Correct 1659 ms 7268 KB Output is correct
29 Correct 1564 ms 7240 KB Output is correct
30 Runtime error 249 ms 16400 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 3660 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 8216 KB Output is correct
2 Correct 717 ms 8228 KB Output is correct
3 Correct 737 ms 8224 KB Output is correct
4 Correct 738 ms 8228 KB Output is correct
5 Correct 762 ms 8224 KB Output is correct
6 Correct 735 ms 8228 KB Output is correct
7 Correct 789 ms 8236 KB Output is correct
8 Correct 754 ms 8260 KB Output is correct
9 Correct 813 ms 8228 KB Output is correct
10 Correct 732 ms 8228 KB Output is correct
11 Correct 726 ms 8220 KB Output is correct
12 Correct 774 ms 8228 KB Output is correct
13 Correct 755 ms 8228 KB Output is correct
14 Correct 749 ms 8228 KB Output is correct
15 Correct 715 ms 8228 KB Output is correct
16 Correct 112 ms 1756 KB Output is correct
17 Correct 100 ms 1876 KB Output is correct
18 Correct 97 ms 1800 KB Output is correct
19 Correct 104 ms 1864 KB Output is correct
20 Correct 110 ms 1740 KB Output is correct
21 Correct 1348 ms 7532 KB Output is correct
22 Correct 1571 ms 7628 KB Output is correct
23 Correct 1566 ms 7500 KB Output is correct
24 Correct 1607 ms 7440 KB Output is correct
25 Correct 1458 ms 7468 KB Output is correct
26 Correct 1695 ms 7284 KB Output is correct
27 Correct 1632 ms 7392 KB Output is correct
28 Correct 1659 ms 7268 KB Output is correct
29 Correct 1564 ms 7240 KB Output is correct
30 Runtime error 249 ms 16400 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -