oj.uz

Submission #199283

# Submission time Handle Problem Language Result Execution time Memory
199283 2020-01-30T22:23:50 Z osaaateiasavtnl Boat (APIO16_boat) C++14
9 / 100
 2000 ms 16376 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 1007, MOD = 1000 * 1000 * 1000 + 7;
int mod(int n) {
    n %= MOD;
    if (n < 0) return n + MOD;
    else return n;
}   
int fp(int a, int p) {
    int ans = 1, c = a;
    for (int i = 0; (1ll << i) <= p; ++i) {
        if ((p >> i) & 1) ans = mod(ans * c);
        c = mod(c * c);
    }   
    return ans;
}   
int dv(int a, int b) { return mod(a * fp(b, MOD - 2)); }
void addmod(int &a, int b) {
    a = mod(a + b);
}   
int C(int n, int k) {
    int a = 1;
    for (int i = n; i > n - k; --i)
        a = mod(a * i);
    int b = 1;
    for (int i = 1; i <= k; ++i)
        b = mod(b * i);
    return dv(a, b);
}   
int n, l[N], r[N], dp[N][N], mem[N][N];
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < N; ++i)
        mem[i][0] = 1;
    for (int i = 1; i < N; ++i)
        for (int j = 1; j < N; ++j)
            mem[i][j] = mod(mem[i - 1][j] + mem[i - 1][j - 1]);
    cin >> n;
    vector <int> c;
    for (int i = 1; i <= n; ++i) {
        cin >> l[i] >> r[i];
        c.app(l[i]); c.app(r[i] + 1);
    }                                
    sort(all(c));
    c.resize(unique(all(c)) - c.begin());
    dp[0][0] = 1;
    for (int i = 0; i + 1 < (int)c.size(); ++i) {
        for (int j = 0; j <= n; ++j) {
            addmod(dp[i + 1][j], dp[i][j]);
            for (int k = j + 1; k <= n; ++k) {
                int ptr = k;
                while (ptr > j && l[ptr] <= c[i] && c[i + 1] - 1 <= r[ptr])
                    --ptr;
                for (int cnt = 1; cnt <= k - ptr; ++cnt) {
                    addmod(dp[i + 1][k], mod(dp[i][j] * mem[k - ptr - 1][cnt - 1]) * C(c[i + 1] - c[i], cnt));
                }   
            }
        }   
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        addmod(ans, dp[c.size() - 1][i]);
    cout << ans << '\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 16248 KB Output is correct
2 Correct 553 ms 16364 KB Output is correct
3 Correct 533 ms 16248 KB Output is correct
4 Correct 535 ms 16120 KB Output is correct
5 Correct 535 ms 16120 KB Output is correct
6 Correct 460 ms 16120 KB Output is correct
7 Correct 437 ms 16248 KB Output is correct
8 Correct 467 ms 16320 KB Output is correct
9 Correct 457 ms 16156 KB Output is correct
10 Correct 458 ms 16252 KB Output is correct
11 Correct 478 ms 16248 KB Output is correct
12 Correct 476 ms 16180 KB Output is correct
13 Correct 453 ms 16376 KB Output is correct
14 Correct 457 ms 16312 KB Output is correct
15 Correct 454 ms 16248 KB Output is correct
16 Correct 119 ms 9720 KB Output is correct
17 Correct 128 ms 9848 KB Output is correct
18 Correct 128 ms 9720 KB Output is correct
19 Correct 130 ms 9864 KB Output is correct
20 Correct 130 ms 9784 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 16248 KB Output is correct
2 Correct 553 ms 16364 KB Output is correct
3 Correct 533 ms 16248 KB Output is correct
4 Correct 535 ms 16120 KB Output is correct
5 Correct 535 ms 16120 KB Output is correct
6 Correct 460 ms 16120 KB Output is correct
7 Correct 437 ms 16248 KB Output is correct
8 Correct 467 ms 16320 KB Output is correct
9 Correct 457 ms 16156 KB Output is correct
10 Correct 458 ms 16252 KB Output is correct
11 Correct 478 ms 16248 KB Output is correct
12 Correct 476 ms 16180 KB Output is correct
13 Correct 453 ms 16376 KB Output is correct
14 Correct 457 ms 16312 KB Output is correct
15 Correct 454 ms 16248 KB Output is correct
16 Correct 119 ms 9720 KB Output is correct
17 Correct 128 ms 9848 KB Output is correct
18 Correct 128 ms 9720 KB Output is correct
19 Correct 130 ms 9864 KB Output is correct
20 Correct 130 ms 9784 KB Output is correct
21 Execution timed out 2081 ms 10448 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 16248 KB Output is correct
2 Correct 553 ms 16364 KB Output is correct
3 Correct 533 ms 16248 KB Output is correct
4 Correct 535 ms 16120 KB Output is correct
5 Correct 535 ms 16120 KB Output is correct
6 Correct 460 ms 16120 KB Output is correct
7 Correct 437 ms 16248 KB Output is correct
8 Correct 467 ms 16320 KB Output is correct
9 Correct 457 ms 16156 KB Output is correct
10 Correct 458 ms 16252 KB Output is correct
11 Correct 478 ms 16248 KB Output is correct
12 Correct 476 ms 16180 KB Output is correct
13 Correct 453 ms 16376 KB Output is correct
14 Correct 457 ms 16312 KB Output is correct
15 Correct 454 ms 16248 KB Output is correct
16 Correct 119 ms 9720 KB Output is correct
17 Correct 128 ms 9848 KB Output is correct
18 Correct 128 ms 9720 KB Output is correct
19 Correct 130 ms 9864 KB Output is correct
20 Correct 130 ms 9784 KB Output is correct
21 Execution timed out 2081 ms 10448 KB Time limit exceeded
22 Halted 0 ms 0 KB -