oj.uz

Submission #199299

# Submission time Handle Problem Language Result Execution time Memory
199299 2020-01-30T22:50:29 Z osaaateiasavtnl Boat (APIO16_boat) C++14
9 / 100
 1406 ms 8672 KB 
#include<bits/stdc++.h>
using namespace std;
#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(long long n) {
    if (n < MOD)
        return n;
    else if (n < 2 * MOD)
        return n - MOD;
    else    
        return n % MOD;
}   
int fp(int a, int p) {
    ll 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((ll)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], lmao[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 mx = 1; mx <= n; ++mx) {
            lmao[mx] = 0;
            for (int cnt = 1; cnt <= mx; ++cnt)
                addmod(lmao[mx], mod((ll)mem[mx - 1][cnt - 1] * cur[cnt]));
        }
        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];
                    addmod(dp[i + 1][k], mod((ll)dp[i][j] * lmao[mx]));
                }   
            }
        }   
    }
    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 1379 ms 8348 KB Output is correct
2 Correct 1393 ms 8336 KB Output is correct
3 Correct 1394 ms 8364 KB Output is correct
4 Correct 1382 ms 8312 KB Output is correct
5 Correct 1406 ms 8672 KB Output is correct
6 Correct 1290 ms 8440 KB Output is correct
7 Correct 1279 ms 8284 KB Output is correct
8 Correct 1285 ms 8444 KB Output is correct
9 Correct 1285 ms 8312 KB Output is correct
10 Correct 1294 ms 8440 KB Output is correct
11 Correct 1307 ms 8240 KB Output is correct
12 Correct 1307 ms 8440 KB Output is correct
13 Correct 1298 ms 8440 KB Output is correct
14 Correct 1280 ms 8424 KB Output is correct
15 Correct 1299 ms 8312 KB Output is correct
16 Correct 257 ms 5060 KB Output is correct
17 Correct 271 ms 5112 KB Output is correct
18 Correct 273 ms 4984 KB Output is correct
19 Correct 284 ms 5244 KB Output is correct
20 Correct 266 ms 5112 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1379 ms 8348 KB Output is correct
2 Correct 1393 ms 8336 KB Output is correct
3 Correct 1394 ms 8364 KB Output is correct
4 Correct 1382 ms 8312 KB Output is correct
5 Correct 1406 ms 8672 KB Output is correct
6 Correct 1290 ms 8440 KB Output is correct
7 Correct 1279 ms 8284 KB Output is correct
8 Correct 1285 ms 8444 KB Output is correct
9 Correct 1285 ms 8312 KB Output is correct
10 Correct 1294 ms 8440 KB Output is correct
11 Correct 1307 ms 8240 KB Output is correct
12 Correct 1307 ms 8440 KB Output is correct
13 Correct 1298 ms 8440 KB Output is correct
14 Correct 1280 ms 8424 KB Output is correct
15 Correct 1299 ms 8312 KB Output is correct
16 Correct 257 ms 5060 KB Output is correct
17 Correct 271 ms 5112 KB Output is correct
18 Correct 273 ms 4984 KB Output is correct
19 Correct 284 ms 5244 KB Output is correct
20 Correct 266 ms 5112 KB Output is correct
21 Incorrect 932 ms 8056 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1379 ms 8348 KB Output is correct
2 Correct 1393 ms 8336 KB Output is correct
3 Correct 1394 ms 8364 KB Output is correct
4 Correct 1382 ms 8312 KB Output is correct
5 Correct 1406 ms 8672 KB Output is correct
6 Correct 1290 ms 8440 KB Output is correct
7 Correct 1279 ms 8284 KB Output is correct
8 Correct 1285 ms 8444 KB Output is correct
9 Correct 1285 ms 8312 KB Output is correct
10 Correct 1294 ms 8440 KB Output is correct
11 Correct 1307 ms 8240 KB Output is correct
12 Correct 1307 ms 8440 KB Output is correct
13 Correct 1298 ms 8440 KB Output is correct
14 Correct 1280 ms 8424 KB Output is correct
15 Correct 1299 ms 8312 KB Output is correct
16 Correct 257 ms 5060 KB Output is correct
17 Correct 271 ms 5112 KB Output is correct
18 Correct 273 ms 4984 KB Output is correct
19 Correct 284 ms 5244 KB Output is correct
20 Correct 266 ms 5112 KB Output is correct
21 Incorrect 932 ms 8056 KB Output isn't correct
22 Halted 0 ms 0 KB -