oj.uz

Submission #1031157

# Submission time Handle Problem Language Result Execution time Memory
1031157 2024-07-22T15:38:23 Z stdfloat Boat (APIO16_boat) C++17
36 / 100
 2000 ms 976 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int md = (int)1e9 + 7;

const int N = (int)1e5 + 1;

vector<int> inv(N);

int pw(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1) res = (ll)res * x % md;

        x = (ll)x * x % md; y >>= 1;
    }

    return res;
}

int C(int n, int r) {
    int x = 1;
    for (int i = 1; i <= r; i++) x = (ll)x * (n - r + i) % md;

    return (ll)x * inv[r] % md;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int x = 1;
    inv[0] = 1;
    for (int i = 1; i < N; i++) {
        x = (ll)x * i % md;
        inv[i] = pw(x, md - 2);
    }

    int n;
    cin >> n;

    map<int, vector<int>> m;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];

        m[a[i]].push_back(i);
        m[b[i] + 1].push_back(-i);
    }

    vector<int> mv;
    for (auto i : m) mv.push_back(i.first);

    set<int> s;
    vector<int> dp(n + 1);
    for (int ii = 0; ii + 1 < (int)mv.size(); ii++) {
        for (auto j : m[mv[ii]]) {
            if (0 < j) s.insert(j);
            else s.erase(-j); 
        }

        int R = mv[ii + 1] - mv[ii];
        vector<int> v(s.begin(), s.end()), nw_dp = dp;
        for (int i = 0; i < (int)v.size(); i++) {
            int sm = 1;
            for (int j = 1; j < v[i]; j++) sm = (sm + dp[j]) % md;

            nw_dp[v[i]] = (dp[v[i]] + (ll)sm * R % md) % md;

            for (int j = 1; j <= min(i, R - 1); j++) {
                int c = C(R, j + 1), sm = 1;
                for (int k = 1; k <= v[i - j]; k++) sm = (sm + dp[k]) % md;
                for (int k = i - j; k >= 0; k--) {
                    int sm = 1;
                    for (int l = 1; l < v[k]; l++) sm = (sm + dp[l]) % md;
                
                    nw_dp[v[i]] = (nw_dp[v[i]] + ((ll)sm * C(i - k - 1, j - 1) % md) * c % md) % md;
                }
            }
        }

        dp = nw_dp;
    }

    int sm = 0;
    for (auto i : dp) sm = (sm + i) % md;

    cout << sm << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 17 ms 852 KB Output is correct
3 Correct 18 ms 860 KB Output is correct
4 Correct 16 ms 856 KB Output is correct
5 Correct 18 ms 936 KB Output is correct
6 Correct 16 ms 856 KB Output is correct
7 Correct 16 ms 852 KB Output is correct
8 Correct 17 ms 860 KB Output is correct
9 Correct 16 ms 860 KB Output is correct
10 Correct 16 ms 860 KB Output is correct
11 Correct 18 ms 860 KB Output is correct
12 Correct 16 ms 860 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 16 ms 860 KB Output is correct
15 Correct 17 ms 860 KB Output is correct
16 Correct 17 ms 848 KB Output is correct
17 Correct 16 ms 860 KB Output is correct
18 Correct 16 ms 860 KB Output is correct
19 Correct 16 ms 860 KB Output is correct
20 Correct 16 ms 860 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 17 ms 852 KB Output is correct
3 Correct 18 ms 860 KB Output is correct
4 Correct 16 ms 856 KB Output is correct
5 Correct 18 ms 936 KB Output is correct
6 Correct 16 ms 856 KB Output is correct
7 Correct 16 ms 852 KB Output is correct
8 Correct 17 ms 860 KB Output is correct
9 Correct 16 ms 860 KB Output is correct
10 Correct 16 ms 860 KB Output is correct
11 Correct 18 ms 860 KB Output is correct
12 Correct 16 ms 860 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 16 ms 860 KB Output is correct
15 Correct 17 ms 860 KB Output is correct
16 Correct 17 ms 848 KB Output is correct
17 Correct 16 ms 860 KB Output is correct
18 Correct 16 ms 860 KB Output is correct
19 Correct 16 ms 860 KB Output is correct
20 Correct 16 ms 860 KB Output is correct
21 Execution timed out 2047 ms 976 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 860 KB Output is correct
2 Correct 143 ms 856 KB Output is correct
3 Correct 226 ms 856 KB Output is correct
4 Correct 261 ms 860 KB Output is correct
5 Correct 334 ms 856 KB Output is correct
6 Correct 1483 ms 856 KB Output is correct
7 Correct 1424 ms 864 KB Output is correct
8 Correct 1382 ms 860 KB Output is correct
9 Correct 1371 ms 860 KB Output is correct
10 Correct 1364 ms 856 KB Output is correct
11 Correct 300 ms 860 KB Output is correct
12 Correct 152 ms 856 KB Output is correct
13 Correct 200 ms 860 KB Output is correct
14 Correct 211 ms 860 KB Output is correct
15 Correct 309 ms 860 KB Output is correct
16 Correct 129 ms 860 KB Output is correct
17 Correct 100 ms 860 KB Output is correct
18 Correct 105 ms 856 KB Output is correct
19 Correct 92 ms 860 KB Output is correct
20 Correct 148 ms 856 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 852 KB Output is correct
2 Correct 17 ms 852 KB Output is correct
3 Correct 18 ms 860 KB Output is correct
4 Correct 16 ms 856 KB Output is correct
5 Correct 18 ms 936 KB Output is correct
6 Correct 16 ms 856 KB Output is correct
7 Correct 16 ms 852 KB Output is correct
8 Correct 17 ms 860 KB Output is correct
9 Correct 16 ms 860 KB Output is correct
10 Correct 16 ms 860 KB Output is correct
11 Correct 18 ms 860 KB Output is correct
12 Correct 16 ms 860 KB Output is correct
13 Correct 16 ms 852 KB Output is correct
14 Correct 16 ms 860 KB Output is correct
15 Correct 17 ms 860 KB Output is correct
16 Correct 17 ms 848 KB Output is correct
17 Correct 16 ms 860 KB Output is correct
18 Correct 16 ms 860 KB Output is correct
19 Correct 16 ms 860 KB Output is correct
20 Correct 16 ms 860 KB Output is correct
21 Execution timed out 2047 ms 976 KB Time limit exceeded
22 Halted 0 ms 0 KB -