oj.uz

Submission #667414

# Submission time Handle Problem Language Result Execution time Memory
667414 2022-12-01T09:38:57 Z Mahdi Boat (APIO16_boat) C++17
36 / 100
 209 ms 14080 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define F first
#define S second
typedef long long ll;
typedef pair<int, int> pii;
const int N=1005, M=1e9+7;
int n, m, a[N], b[N], dp[N][2*N], c[2*N][N], en[N][N], h[2*N][N];
vector<int>v;

int tav(int x, int p){
    int res=1;
    while(p){
        if(p&1)
            res=1LL*res*x%M;
        x=1LL*x*x%M;
        p>>=1;
    }
    return res;
}

void pre(){
    en[0][0]=1;
    for(int i=1;i<=n;++i){
        en[i][0]=1;
        for(int j=1;j<=i;++j){
            en[i][j]=en[i-1][j]+en[i-1][j-1];
            if(en[i][j]>=M)
                en[i][j]-=M;
        }
    }
    for(int i=0;i<m;++i){
        int x=v[i+1]-v[i];
        c[i][0]=1;
        for(int j=1;j<=min(n, x);++j){
            c[i][j]=1LL*c[i][j-1]*(x-j+1)%M;
            c[i][j]=1LL*c[i][j]*tav(j, M-2)%M;
        }
    }
    for(int i=0;i<m;++i){
        h[i][1]=c[i][1];
        for(int j=2;j<=min(n, v[i+1]-v[i]);++j){
            ll z=0;
            for(int k=0;k<=j-2;++k)
                z+=1LL*en[j-2][k]*c[i][k+2]%M;
            h[i][j]=z%M;
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(++b[i]);
    }
    sort(all(v));
    v.resize(int(unique(all(v))-v.begin()));
    m=(int)v.size()-1;
    pre();
    for(int i=0;i<m;++i)
        dp[0][i]=1;
    for(int i=1;i<=n;++i){
        ll x=dp[i-1][0];
        if(a[i]<=v[0]){
            int tt=0;
            for(int j=i;j>=1;--j){
                if(a[j]<=v[0])
                    x+=h[0][++tt];
            }
        }
        dp[i][0]=x%M;
        for(int j=1;j<m;++j){
            x=dp[i-1][j]+dp[i][j-1];
            x+=M-dp[i-1][j-1];
            if(a[i]<=v[j] && b[i]>=v[j+1]){
                int tt=0;
                for(int k=i;k>=1;--k){
                    if(a[k]<=v[j] && b[k]>=v[j+1])
                        x+=1LL*h[j][++tt]*dp[k-1][j-1]%M;
                }
            }
            dp[i][j]=x%M;
        }
    }
    cout<<(dp[n][m-1]+M-1)%M<<'\n';
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 13984 KB Output is correct
2 Correct 208 ms 14004 KB Output is correct
3 Correct 174 ms 14028 KB Output is correct
4 Correct 179 ms 14080 KB Output is correct
5 Correct 187 ms 13976 KB Output is correct
6 Correct 176 ms 13996 KB Output is correct
7 Correct 174 ms 13988 KB Output is correct
8 Correct 209 ms 14036 KB Output is correct
9 Correct 185 ms 14068 KB Output is correct
10 Correct 193 ms 14032 KB Output is correct
11 Correct 167 ms 14000 KB Output is correct
12 Correct 172 ms 14032 KB Output is correct
13 Correct 186 ms 14020 KB Output is correct
14 Correct 181 ms 14020 KB Output is correct
15 Correct 168 ms 14008 KB Output is correct
16 Correct 41 ms 6008 KB Output is correct
17 Correct 44 ms 6236 KB Output is correct
18 Correct 32 ms 6076 KB Output is correct
19 Correct 34 ms 6160 KB Output is correct
20 Correct 34 ms 6016 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 13984 KB Output is correct
2 Correct 208 ms 14004 KB Output is correct
3 Correct 174 ms 14028 KB Output is correct
4 Correct 179 ms 14080 KB Output is correct
5 Correct 187 ms 13976 KB Output is correct
6 Correct 176 ms 13996 KB Output is correct
7 Correct 174 ms 13988 KB Output is correct
8 Correct 209 ms 14036 KB Output is correct
9 Correct 185 ms 14068 KB Output is correct
10 Correct 193 ms 14032 KB Output is correct
11 Correct 167 ms 14000 KB Output is correct
12 Correct 172 ms 14032 KB Output is correct
13 Correct 186 ms 14020 KB Output is correct
14 Correct 181 ms 14020 KB Output is correct
15 Correct 168 ms 14008 KB Output is correct
16 Correct 41 ms 6008 KB Output is correct
17 Correct 44 ms 6236 KB Output is correct
18 Correct 32 ms 6076 KB Output is correct
19 Correct 34 ms 6160 KB Output is correct
20 Correct 34 ms 6016 KB Output is correct
21 Incorrect 102 ms 13144 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2776 KB Output is correct
2 Correct 8 ms 2772 KB Output is correct
3 Correct 7 ms 2772 KB Output is correct
4 Correct 8 ms 2752 KB Output is correct
5 Correct 7 ms 2772 KB Output is correct
6 Correct 11 ms 2720 KB Output is correct
7 Correct 11 ms 2772 KB Output is correct
8 Correct 8 ms 2772 KB Output is correct
9 Correct 8 ms 2772 KB Output is correct
10 Correct 8 ms 2772 KB Output is correct
11 Correct 7 ms 2772 KB Output is correct
12 Correct 7 ms 2772 KB Output is correct
13 Correct 7 ms 2772 KB Output is correct
14 Correct 7 ms 2772 KB Output is correct
15 Correct 7 ms 2772 KB Output is correct
16 Correct 5 ms 2004 KB Output is correct
17 Correct 4 ms 2020 KB Output is correct
18 Correct 4 ms 2004 KB Output is correct
19 Correct 4 ms 2004 KB Output is correct
20 Correct 4 ms 1944 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 13984 KB Output is correct
2 Correct 208 ms 14004 KB Output is correct
3 Correct 174 ms 14028 KB Output is correct
4 Correct 179 ms 14080 KB Output is correct
5 Correct 187 ms 13976 KB Output is correct
6 Correct 176 ms 13996 KB Output is correct
7 Correct 174 ms 13988 KB Output is correct
8 Correct 209 ms 14036 KB Output is correct
9 Correct 185 ms 14068 KB Output is correct
10 Correct 193 ms 14032 KB Output is correct
11 Correct 167 ms 14000 KB Output is correct
12 Correct 172 ms 14032 KB Output is correct
13 Correct 186 ms 14020 KB Output is correct
14 Correct 181 ms 14020 KB Output is correct
15 Correct 168 ms 14008 KB Output is correct
16 Correct 41 ms 6008 KB Output is correct
17 Correct 44 ms 6236 KB Output is correct
18 Correct 32 ms 6076 KB Output is correct
19 Correct 34 ms 6160 KB Output is correct
20 Correct 34 ms 6016 KB Output is correct
21 Incorrect 102 ms 13144 KB Output isn't correct
22 Halted 0 ms 0 KB -