oj.uz

Submission #199288

# Submission time Handle Problem Language Result Execution time Memory
199288 2020-01-30T22:36:39 Z osaaateiasavtnl Boat (APIO16_boat) C++14
36 / 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) {
    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];
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 = 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 = 0;
                    for (int t = j + 1; t <= k; ++t)
                        mx += l[t] <= c[i] && c[i + 1] - 1 <= r[t];
                    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 1111 ms 16308 KB Output is correct
2 Correct 1105 ms 16376 KB Output is correct
3 Correct 1115 ms 16352 KB Output is correct
4 Correct 1115 ms 16236 KB Output is correct
5 Correct 1128 ms 16248 KB Output is correct
6 Correct 1053 ms 16248 KB Output is correct
7 Correct 1038 ms 16364 KB Output is correct
8 Correct 1046 ms 16236 KB Output is correct
9 Correct 1048 ms 16232 KB Output is correct
10 Correct 1036 ms 16248 KB Output is correct
11 Correct 1031 ms 16248 KB Output is correct
12 Correct 1041 ms 16376 KB Output is correct
13 Correct 1035 ms 16376 KB Output is correct
14 Correct 1033 ms 16248 KB Output is correct
15 Correct 1024 ms 16140 KB Output is correct
16 Correct 239 ms 9720 KB Output is correct
17 Correct 251 ms 9952 KB Output is correct
18 Correct 244 ms 9720 KB Output is correct
19 Correct 258 ms 9936 KB Output is correct
20 Correct 247 ms 9720 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 16308 KB Output is correct
2 Correct 1105 ms 16376 KB Output is correct
3 Correct 1115 ms 16352 KB Output is correct
4 Correct 1115 ms 16236 KB Output is correct
5 Correct 1128 ms 16248 KB Output is correct
6 Correct 1053 ms 16248 KB Output is correct
7 Correct 1038 ms 16364 KB Output is correct
8 Correct 1046 ms 16236 KB Output is correct
9 Correct 1048 ms 16232 KB Output is correct
10 Correct 1036 ms 16248 KB Output is correct
11 Correct 1031 ms 16248 KB Output is correct
12 Correct 1041 ms 16376 KB Output is correct
13 Correct 1035 ms 16376 KB Output is correct
14 Correct 1033 ms 16248 KB Output is correct
15 Correct 1024 ms 16140 KB Output is correct
16 Correct 239 ms 9720 KB Output is correct
17 Correct 251 ms 9952 KB Output is correct
18 Correct 244 ms 9720 KB Output is correct
19 Correct 258 ms 9936 KB Output is correct
20 Correct 247 ms 9720 KB Output is correct
21 Execution timed out 2078 ms 9964 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9208 KB Output is correct
2 Correct 69 ms 9208 KB Output is correct
3 Correct 74 ms 9208 KB Output is correct
4 Correct 82 ms 9336 KB Output is correct
5 Correct 84 ms 9336 KB Output is correct
6 Correct 128 ms 9336 KB Output is correct
7 Correct 120 ms 9208 KB Output is correct
8 Correct 125 ms 9336 KB Output is correct
9 Correct 129 ms 9208 KB Output is correct
10 Correct 125 ms 9228 KB Output is correct
11 Correct 73 ms 9300 KB Output is correct
12 Correct 60 ms 9208 KB Output is correct
13 Correct 61 ms 9336 KB Output is correct
14 Correct 66 ms 9208 KB Output is correct
15 Correct 74 ms 9208 KB Output is correct
16 Correct 51 ms 8952 KB Output is correct
17 Correct 46 ms 8824 KB Output is correct
18 Correct 48 ms 8824 KB Output is correct
19 Correct 48 ms 8828 KB Output is correct
20 Correct 56 ms 8824 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1111 ms 16308 KB Output is correct
2 Correct 1105 ms 16376 KB Output is correct
3 Correct 1115 ms 16352 KB Output is correct
4 Correct 1115 ms 16236 KB Output is correct
5 Correct 1128 ms 16248 KB Output is correct
6 Correct 1053 ms 16248 KB Output is correct
7 Correct 1038 ms 16364 KB Output is correct
8 Correct 1046 ms 16236 KB Output is correct
9 Correct 1048 ms 16232 KB Output is correct
10 Correct 1036 ms 16248 KB Output is correct
11 Correct 1031 ms 16248 KB Output is correct
12 Correct 1041 ms 16376 KB Output is correct
13 Correct 1035 ms 16376 KB Output is correct
14 Correct 1033 ms 16248 KB Output is correct
15 Correct 1024 ms 16140 KB Output is correct
16 Correct 239 ms 9720 KB Output is correct
17 Correct 251 ms 9952 KB Output is correct
18 Correct 244 ms 9720 KB Output is correct
19 Correct 258 ms 9936 KB Output is correct
20 Correct 247 ms 9720 KB Output is correct
21 Execution timed out 2078 ms 9964 KB Time limit exceeded
22 Halted 0 ms 0 KB -