oj.uz

Submission #1088751

# Submission time Handle Problem Language Result Execution time Memory
1088751 2024-09-15T01:20:43 Z vjudge1 Boat (APIO16_boat) C++17
100 / 100
 853 ms 21076 KB 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)
 
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
 
 
constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/
 
template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }
 
template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
#define MAX             2505
#define LIM             5005
int nArr;
vector<int> seg;
int l[MAX], r[MAX];
 
int dp[MAX * 2][MAX];
int inv[MAX];
int power(int a, int exp){
    int res = 1;
    for (; exp > 0; exp >>= 1, a = (1LL * a * a) % Mod) if(exp & 1){
        res = (1LL * res * a) % Mod;
    }
    return res;
}
void add(int &x, int y){
    x += y;
    if (x >= Mod) x %= Mod;
    while(x < 0) x += Mod;
}
 
int mul(int x, int y){
    return 1LL * x * y % Mod;
}
 
void process(void){
    cin >> nArr;
    for (int i = 1; i <= nArr; ++i){
        cin >> l[i] >> r[i];
        seg.emplace_back(l[i]);
        seg.emplace_back(r[i] + 1);
    }
 
    seg.emplace_back(0);
    sort(seg.begin(), seg.end());
    seg.resize(unique(seg.begin(), seg.end()) - seg.begin());
 
    for (int i = 0; i <= nArr; ++i) inv[i] = power(i, Mod - 2);
    for (int i = 0; i <= nArr; ++i) dp[0][i] = 1;
    int n = (int)seg.size();
 
    for (int i = 1; i < n - 1; ++i){
        int x = seg[i + 1] - seg[i];
        for (int pos = 0; pos <= nArr; ++pos){
            dp[i][pos] = dp[i - 1][pos];
            int nCk = 1, cnt = 0;
            for (int last = pos; last >= 1; --last){
                if (l[last] <= seg[i] && seg[i + 1] - 1 <= r[last]){
                    ++cnt;
                    nCk = mul(nCk, x + cnt - 1) * inv[cnt] % Mod;
                    add(dp[i][pos], mul(dp[i - 1][last - 1], nCk));
//                    add(dp[i][pos], mul(dp[i - 1][last - 1], C[x + cnt - 1][cnt]));
                }
            }
        }
    }
    /*
        C(x + cnt - 1, cnt)
 
        (x + cnt - 1)! / cnt! . (x - 1)!
 
        (x - 1 + 1) * (x - 1 + 2) .. * (x - 1 + cnt) / cnt!
 
    */
    cout << (dp[n - 2][nArr] - 1 + Mod) % Mod;
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 19536 KB Output is correct
2 Correct 132 ms 17980 KB Output is correct
3 Correct 126 ms 18004 KB Output is correct
4 Correct 123 ms 19260 KB Output is correct
5 Correct 127 ms 18004 KB Output is correct
6 Correct 102 ms 18004 KB Output is correct
7 Correct 102 ms 16960 KB Output is correct
8 Correct 105 ms 17224 KB Output is correct
9 Correct 102 ms 19284 KB Output is correct
10 Correct 110 ms 18004 KB Output is correct
11 Correct 103 ms 17992 KB Output is correct
12 Correct 105 ms 17984 KB Output is correct
13 Correct 105 ms 19284 KB Output is correct
14 Correct 98 ms 17992 KB Output is correct
15 Correct 103 ms 18004 KB Output is correct
16 Correct 22 ms 4440 KB Output is correct
17 Correct 23 ms 4700 KB Output is correct
18 Correct 26 ms 4440 KB Output is correct
19 Correct 23 ms 4444 KB Output is correct
20 Correct 23 ms 4680 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 19536 KB Output is correct
2 Correct 132 ms 17980 KB Output is correct
3 Correct 126 ms 18004 KB Output is correct
4 Correct 123 ms 19260 KB Output is correct
5 Correct 127 ms 18004 KB Output is correct
6 Correct 102 ms 18004 KB Output is correct
7 Correct 102 ms 16960 KB Output is correct
8 Correct 105 ms 17224 KB Output is correct
9 Correct 102 ms 19284 KB Output is correct
10 Correct 110 ms 18004 KB Output is correct
11 Correct 103 ms 17992 KB Output is correct
12 Correct 105 ms 17984 KB Output is correct
13 Correct 105 ms 19284 KB Output is correct
14 Correct 98 ms 17992 KB Output is correct
15 Correct 103 ms 18004 KB Output is correct
16 Correct 22 ms 4440 KB Output is correct
17 Correct 23 ms 4700 KB Output is correct
18 Correct 26 ms 4440 KB Output is correct
19 Correct 23 ms 4444 KB Output is correct
20 Correct 23 ms 4680 KB Output is correct
21 Correct 528 ms 16188 KB Output is correct
22 Correct 529 ms 19012 KB Output is correct
23 Correct 493 ms 17236 KB Output is correct
24 Correct 526 ms 18996 KB Output is correct
25 Correct 547 ms 17236 KB Output is correct
26 Correct 712 ms 19028 KB Output is correct
27 Correct 727 ms 17212 KB Output is correct
28 Correct 719 ms 17220 KB Output is correct
29 Correct 722 ms 14664 KB Output is correct
30 Correct 117 ms 15700 KB Output is correct
31 Correct 105 ms 16980 KB Output is correct
32 Correct 108 ms 16712 KB Output is correct
33 Correct 113 ms 16960 KB Output is correct
34 Correct 109 ms 18000 KB Output is correct
35 Correct 121 ms 19280 KB Output is correct
36 Correct 128 ms 15696 KB Output is correct
37 Correct 122 ms 19284 KB Output is correct
38 Correct 121 ms 19284 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4444 KB Output is correct
2 Correct 5 ms 4444 KB Output is correct
3 Correct 6 ms 4564 KB Output is correct
4 Correct 6 ms 4444 KB Output is correct
5 Correct 6 ms 4444 KB Output is correct
6 Correct 8 ms 4632 KB Output is correct
7 Correct 8 ms 4444 KB Output is correct
8 Correct 8 ms 4444 KB Output is correct
9 Correct 8 ms 4632 KB Output is correct
10 Correct 8 ms 4624 KB Output is correct
11 Correct 7 ms 4628 KB Output is correct
12 Correct 6 ms 4628 KB Output is correct
13 Correct 6 ms 4632 KB Output is correct
14 Correct 6 ms 4628 KB Output is correct
15 Correct 6 ms 4632 KB Output is correct
16 Correct 4 ms 4444 KB Output is correct
17 Correct 4 ms 2396 KB Output is correct
18 Correct 3 ms 4628 KB Output is correct
19 Correct 3 ms 4620 KB Output is correct
20 Correct 4 ms 2396 KB Output is correct

Subtask #4
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 19536 KB Output is correct
2 Correct 132 ms 17980 KB Output is correct
3 Correct 126 ms 18004 KB Output is correct
4 Correct 123 ms 19260 KB Output is correct
5 Correct 127 ms 18004 KB Output is correct
6 Correct 102 ms 18004 KB Output is correct
7 Correct 102 ms 16960 KB Output is correct
8 Correct 105 ms 17224 KB Output is correct
9 Correct 102 ms 19284 KB Output is correct
10 Correct 110 ms 18004 KB Output is correct
11 Correct 103 ms 17992 KB Output is correct
12 Correct 105 ms 17984 KB Output is correct
13 Correct 105 ms 19284 KB Output is correct
14 Correct 98 ms 17992 KB Output is correct
15 Correct 103 ms 18004 KB Output is correct
16 Correct 22 ms 4440 KB Output is correct
17 Correct 23 ms 4700 KB Output is correct
18 Correct 26 ms 4440 KB Output is correct
19 Correct 23 ms 4444 KB Output is correct
20 Correct 23 ms 4680 KB Output is correct
21 Correct 528 ms 16188 KB Output is correct
22 Correct 529 ms 19012 KB Output is correct
23 Correct 493 ms 17236 KB Output is correct
24 Correct 526 ms 18996 KB Output is correct
25 Correct 547 ms 17236 KB Output is correct
26 Correct 712 ms 19028 KB Output is correct
27 Correct 727 ms 17212 KB Output is correct
28 Correct 719 ms 17220 KB Output is correct
29 Correct 722 ms 14664 KB Output is correct
30 Correct 117 ms 15700 KB Output is correct
31 Correct 105 ms 16980 KB Output is correct
32 Correct 108 ms 16712 KB Output is correct
33 Correct 113 ms 16960 KB Output is correct
34 Correct 109 ms 18000 KB Output is correct
35 Correct 121 ms 19280 KB Output is correct
36 Correct 128 ms 15696 KB Output is correct
37 Correct 122 ms 19284 KB Output is correct
38 Correct 121 ms 19284 KB Output is correct
39 Correct 6 ms 4444 KB Output is correct
40 Correct 5 ms 4444 KB Output is correct
41 Correct 6 ms 4564 KB Output is correct
42 Correct 6 ms 4444 KB Output is correct
43 Correct 6 ms 4444 KB Output is correct
44 Correct 8 ms 4632 KB Output is correct
45 Correct 8 ms 4444 KB Output is correct
46 Correct 8 ms 4444 KB Output is correct
47 Correct 8 ms 4632 KB Output is correct
48 Correct 8 ms 4624 KB Output is correct
49 Correct 7 ms 4628 KB Output is correct
50 Correct 6 ms 4628 KB Output is correct
51 Correct 6 ms 4632 KB Output is correct
52 Correct 6 ms 4628 KB Output is correct
53 Correct 6 ms 4632 KB Output is correct
54 Correct 4 ms 4444 KB Output is correct
55 Correct 4 ms 2396 KB Output is correct
56 Correct 3 ms 4628 KB Output is correct
57 Correct 3 ms 4620 KB Output is correct
58 Correct 4 ms 2396 KB Output is correct
59 Correct 619 ms 16968 KB Output is correct
60 Correct 580 ms 18000 KB Output is correct
61 Correct 573 ms 16956 KB Output is correct
62 Correct 631 ms 19284 KB Output is correct
63 Correct 594 ms 17988 KB Output is correct
64 Correct 848 ms 18000 KB Output is correct
65 Correct 849 ms 19252 KB Output is correct
66 Correct 849 ms 21052 KB Output is correct
67 Correct 847 ms 21044 KB Output is correct
68 Correct 853 ms 21048 KB Output is correct
69 Correct 616 ms 21060 KB Output is correct
70 Correct 631 ms 21076 KB Output is correct
71 Correct 642 ms 21076 KB Output is correct
72 Correct 648 ms 21072 KB Output is correct
73 Correct 646 ms 21044 KB Output is correct
74 Correct 105 ms 4436 KB Output is correct
75 Correct 107 ms 4688 KB Output is correct
76 Correct 107 ms 4432 KB Output is correct
77 Correct 109 ms 4420 KB Output is correct
78 Correct 104 ms 4432 KB Output is correct