oj.uz

Submission #199289

# Submission time Handle Problem Language Result Execution time Memory
199289 2020-01-30T22:38:42 Z osaaateiasavtnl Boat (APIO16_boat) C++14
36 / 100
 2000 ms 16456 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) {
    if (n < k)
        return 0;
    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], cur[N], pref[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)
            cur[j] = C(c[i + 1] - c[i], j);
        for (int j = 1; j <= n; ++j)
            pref[j] = pref[j - 1] + (l[j] <= c[i] && c[i + 1] - 1 <= r[j]);
        for (int j = 0; j <= n; ++j) {
            addmod(dp[i + 1][j], dp[i][j]);
            for (int k = j + 1; k <= n; ++k) {
                if (l[k] <= c[i] && c[i + 1] - 1 <= r[k]) {
                    int mx = pref[k] - pref[j];
                    for (int cnt = 1; cnt <= mx; ++cnt)
                        addmod(dp[i + 1][k], mod(dp[i][j] * mem[mx - 1][cnt - 1]) * cur[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 1000 ms 16376 KB Output is correct
2 Correct 1004 ms 16168 KB Output is correct
3 Correct 1002 ms 16376 KB Output is correct
4 Correct 1046 ms 16380 KB Output is correct
5 Correct 999 ms 16376 KB Output is correct
6 Correct 942 ms 16376 KB Output is correct
7 Correct 943 ms 16240 KB Output is correct
8 Correct 945 ms 16248 KB Output is correct
9 Correct 942 ms 16456 KB Output is correct
10 Correct 945 ms 16376 KB Output is correct
11 Correct 947 ms 16388 KB Output is correct
12 Correct 947 ms 16248 KB Output is correct
13 Correct 946 ms 16248 KB Output is correct
14 Correct 949 ms 16380 KB Output is correct
15 Correct 944 ms 16376 KB Output is correct
16 Correct 191 ms 9720 KB Output is correct
17 Correct 206 ms 9848 KB Output is correct
18 Correct 199 ms 9848 KB Output is correct
19 Correct 203 ms 9848 KB Output is correct
20 Correct 194 ms 9824 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 16376 KB Output is correct
2 Correct 1004 ms 16168 KB Output is correct
3 Correct 1002 ms 16376 KB Output is correct
4 Correct 1046 ms 16380 KB Output is correct
5 Correct 999 ms 16376 KB Output is correct
6 Correct 942 ms 16376 KB Output is correct
7 Correct 943 ms 16240 KB Output is correct
8 Correct 945 ms 16248 KB Output is correct
9 Correct 942 ms 16456 KB Output is correct
10 Correct 945 ms 16376 KB Output is correct
11 Correct 947 ms 16388 KB Output is correct
12 Correct 947 ms 16248 KB Output is correct
13 Correct 946 ms 16248 KB Output is correct
14 Correct 949 ms 16380 KB Output is correct
15 Correct 944 ms 16376 KB Output is correct
16 Correct 191 ms 9720 KB Output is correct
17 Correct 206 ms 9848 KB Output is correct
18 Correct 199 ms 9848 KB Output is correct
19 Correct 203 ms 9848 KB Output is correct
20 Correct 194 ms 9824 KB Output is correct
21 Execution timed out 2084 ms 10500 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 9336 KB Output is correct
2 Correct 51 ms 9208 KB Output is correct
3 Correct 56 ms 9208 KB Output is correct
4 Correct 61 ms 9240 KB Output is correct
5 Correct 64 ms 9336 KB Output is correct
6 Correct 104 ms 9300 KB Output is correct
7 Correct 106 ms 9336 KB Output is correct
8 Correct 104 ms 9208 KB Output is correct
9 Correct 108 ms 9216 KB Output is correct
10 Correct 108 ms 9208 KB Output is correct
11 Correct 60 ms 9208 KB Output is correct
12 Correct 49 ms 9212 KB Output is correct
13 Correct 52 ms 9208 KB Output is correct
14 Correct 53 ms 9208 KB Output is correct
15 Correct 60 ms 9212 KB Output is correct
16 Correct 40 ms 8824 KB Output is correct
17 Correct 36 ms 8824 KB Output is correct
18 Correct 38 ms 8824 KB Output is correct
19 Correct 36 ms 8824 KB Output is correct
20 Correct 43 ms 8824 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 16376 KB Output is correct
2 Correct 1004 ms 16168 KB Output is correct
3 Correct 1002 ms 16376 KB Output is correct
4 Correct 1046 ms 16380 KB Output is correct
5 Correct 999 ms 16376 KB Output is correct
6 Correct 942 ms 16376 KB Output is correct
7 Correct 943 ms 16240 KB Output is correct
8 Correct 945 ms 16248 KB Output is correct
9 Correct 942 ms 16456 KB Output is correct
10 Correct 945 ms 16376 KB Output is correct
11 Correct 947 ms 16388 KB Output is correct
12 Correct 947 ms 16248 KB Output is correct
13 Correct 946 ms 16248 KB Output is correct
14 Correct 949 ms 16380 KB Output is correct
15 Correct 944 ms 16376 KB Output is correct
16 Correct 191 ms 9720 KB Output is correct
17 Correct 206 ms 9848 KB Output is correct
18 Correct 199 ms 9848 KB Output is correct
19 Correct 203 ms 9848 KB Output is correct
20 Correct 194 ms 9824 KB Output is correct
21 Execution timed out 2084 ms 10500 KB Time limit exceeded
22 Halted 0 ms 0 KB -