oj.uz

Submission #545635

# Submission time Handle Problem Language Result Execution time Memory
545635 2022-04-05T04:27:29 Z flashhh Boat (APIO16_boat) C++14
27 / 100
 7 ms 12116 KB 
#include <bits/stdc++.h>
#define ll long long
#define N 505
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back

const int oo = 1e9 + 7;

using namespace std;

int n,m;
pii a[N],b[N];
ll res,inv[N],dp[N][N*4],pre[N][N*4];
vector<int> lvt;

ll power(ll x,int y) {
    if (y == 0) return 1;

    ll tam = power(x*x %oo, y>>1);
    if (y&1) tam = tam * x %oo;

    return tam;
}

int main()
{
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    ios_base::sync_with_stdio (0); cin.tie (0); cout.tie (0);

    cin >> n;
    for (int i=1;i<=n;++i) {
        cin >> a[i].fi >> a[i].se;
        lvt.pb(a[i].fi); lvt.pb(a[i].se);
    }

    sort(lvt.begin(),lvt.end());
    lvt.resize(unique(lvt.begin(),lvt.end())-lvt.begin());

    for (int e=0;e<(int)lvt.size();++e) {
        b[++m] = {lvt[e],lvt[e]};
        if (e < (int)lvt.size() - 1 && lvt[e]+1 < lvt[e+1]) b[++m] = {lvt[e]+1,lvt[e+1]-1};
    }

    dp[0][0] = 1;
    for (int i=0;i<=n;++i) pre[i][0] = 1;
    for (int j=0;j<=m;++j) pre[0][j] = 1;

    for (int i=1;i<=n;++i) inv[i] = power(i,oo-2);

    for (int i=1;i<=n;++i)
        for (int j=1;j<=m;++j) {
            dp[i][j] = dp[i][j-1];
            if (a[i].fi > b[j].se || a[i].se < b[j].fi) {
                pre[i][j] = (pre[i-1][j] + dp[i][j]) %oo;
                continue;
            }

            int len = b[j].se - b[j].fi + 1; int num = -1;
            ll C = len - 1;

            dp[i][j] = (dp[i][j] + pre[i-1][j-1] * len) %oo;

            if (len >= 2) {
                for (int k=2;k<=i;++k) {
                    if (a[i-k+1].fi > b[j].se || a[i-k+1].se < b[j].fi) continue;

                    ++num;
                    C = C * (num + len) %oo * inv[num+2] %oo;

                    dp[i][j] = (dp[i][j] + pre[i-k][j-1] * C) %oo;
                }
            }

            pre[i][j] = (pre[i-1][j] + dp[i][j]) %oo;
        }

    for (int i=1;i<=n;++i) res = (res + dp[i][m]) %oo;
    cout << res;

    return 0;
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1748 KB Output is correct
2 Correct 3 ms 1748 KB Output is correct
3 Correct 3 ms 1748 KB Output is correct
4 Correct 3 ms 1748 KB Output is correct
5 Correct 3 ms 1772 KB Output is correct
6 Correct 5 ms 1748 KB Output is correct
7 Correct 5 ms 1748 KB Output is correct
8 Correct 5 ms 1748 KB Output is correct
9 Correct 5 ms 1748 KB Output is correct
10 Correct 5 ms 1736 KB Output is correct
11 Correct 3 ms 1748 KB Output is correct
12 Correct 2 ms 1748 KB Output is correct
13 Correct 3 ms 1748 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 3 ms 1748 KB Output is correct
16 Correct 2 ms 1364 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 2 ms 1364 KB Output is correct
19 Correct 2 ms 1364 KB Output is correct
20 Correct 2 ms 1348 KB Output is correct

Subtask #4
0 / 42.0

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