oj.uz

Submission #667405

# Submission time Handle Problem Language Result Execution time Memory
667405 2022-12-01T09:32:09 Z Mahdi Boat (APIO16_boat) C++17
9 / 100
 307 ms 7384 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=505, 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<=n;++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]+1);
    }
    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]){
            for(int j=i;j>=1;--j)
                x+=h[0][i-j+1];
        }
        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]+1>=v[j+1]){
                int tt=0;
                for(int k=i;k>=1;--k){
                    if(a[k]<=v[j] && b[k]+1>=v[j+1]){
                        ++tt;
                        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 277 ms 7116 KB Output is correct
2 Correct 278 ms 7116 KB Output is correct
3 Correct 280 ms 7116 KB Output is correct
4 Correct 278 ms 7212 KB Output is correct
5 Correct 284 ms 7116 KB Output is correct
6 Correct 279 ms 7152 KB Output is correct
7 Correct 276 ms 7168 KB Output is correct
8 Correct 283 ms 7384 KB Output is correct
9 Correct 280 ms 7116 KB Output is correct
10 Correct 276 ms 7208 KB Output is correct
11 Correct 281 ms 7208 KB Output is correct
12 Correct 287 ms 7216 KB Output is correct
13 Correct 284 ms 7308 KB Output is correct
14 Correct 282 ms 7208 KB Output is correct
15 Correct 274 ms 7152 KB Output is correct
16 Correct 51 ms 3912 KB Output is correct
17 Correct 56 ms 3956 KB Output is correct
18 Correct 54 ms 3988 KB Output is correct
19 Correct 56 ms 4000 KB Output is correct
20 Correct 54 ms 3976 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 7116 KB Output is correct
2 Correct 278 ms 7116 KB Output is correct
3 Correct 280 ms 7116 KB Output is correct
4 Correct 278 ms 7212 KB Output is correct
5 Correct 284 ms 7116 KB Output is correct
6 Correct 279 ms 7152 KB Output is correct
7 Correct 276 ms 7168 KB Output is correct
8 Correct 283 ms 7384 KB Output is correct
9 Correct 280 ms 7116 KB Output is correct
10 Correct 276 ms 7208 KB Output is correct
11 Correct 281 ms 7208 KB Output is correct
12 Correct 287 ms 7216 KB Output is correct
13 Correct 284 ms 7308 KB Output is correct
14 Correct 282 ms 7208 KB Output is correct
15 Correct 274 ms 7152 KB Output is correct
16 Correct 51 ms 3912 KB Output is correct
17 Correct 56 ms 3956 KB Output is correct
18 Correct 54 ms 3988 KB Output is correct
19 Correct 56 ms 4000 KB Output is correct
20 Correct 54 ms 3976 KB Output is correct
21 Incorrect 307 ms 6792 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 7116 KB Output is correct
2 Correct 278 ms 7116 KB Output is correct
3 Correct 280 ms 7116 KB Output is correct
4 Correct 278 ms 7212 KB Output is correct
5 Correct 284 ms 7116 KB Output is correct
6 Correct 279 ms 7152 KB Output is correct
7 Correct 276 ms 7168 KB Output is correct
8 Correct 283 ms 7384 KB Output is correct
9 Correct 280 ms 7116 KB Output is correct
10 Correct 276 ms 7208 KB Output is correct
11 Correct 281 ms 7208 KB Output is correct
12 Correct 287 ms 7216 KB Output is correct
13 Correct 284 ms 7308 KB Output is correct
14 Correct 282 ms 7208 KB Output is correct
15 Correct 274 ms 7152 KB Output is correct
16 Correct 51 ms 3912 KB Output is correct
17 Correct 56 ms 3956 KB Output is correct
18 Correct 54 ms 3988 KB Output is correct
19 Correct 56 ms 4000 KB Output is correct
20 Correct 54 ms 3976 KB Output is correct
21 Incorrect 307 ms 6792 KB Output isn't correct
22 Halted 0 ms 0 KB -