oj.uz

Submission #667411

# Submission time Handle Problem Language Result Execution time Memory
667411 2022-12-01T09:38:02 Z Mahdi Boat (APIO16_boat) C++17
36 / 100
 175 ms 7320 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<=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 163 ms 7116 KB Output is correct
2 Correct 155 ms 7120 KB Output is correct
3 Correct 154 ms 7220 KB Output is correct
4 Correct 154 ms 7204 KB Output is correct
5 Correct 156 ms 7200 KB Output is correct
6 Correct 154 ms 7116 KB Output is correct
7 Correct 158 ms 7132 KB Output is correct
8 Correct 158 ms 7204 KB Output is correct
9 Correct 159 ms 7176 KB Output is correct
10 Correct 165 ms 7112 KB Output is correct
11 Correct 152 ms 7204 KB Output is correct
12 Correct 155 ms 7160 KB Output is correct
13 Correct 154 ms 7144 KB Output is correct
14 Correct 156 ms 7320 KB Output is correct
15 Correct 175 ms 7232 KB Output is correct
16 Correct 29 ms 3908 KB Output is correct
17 Correct 32 ms 3984 KB Output is correct
18 Correct 33 ms 3920 KB Output is correct
19 Correct 31 ms 4012 KB Output is correct
20 Correct 30 ms 4004 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 7116 KB Output is correct
2 Correct 155 ms 7120 KB Output is correct
3 Correct 154 ms 7220 KB Output is correct
4 Correct 154 ms 7204 KB Output is correct
5 Correct 156 ms 7200 KB Output is correct
6 Correct 154 ms 7116 KB Output is correct
7 Correct 158 ms 7132 KB Output is correct
8 Correct 158 ms 7204 KB Output is correct
9 Correct 159 ms 7176 KB Output is correct
10 Correct 165 ms 7112 KB Output is correct
11 Correct 152 ms 7204 KB Output is correct
12 Correct 155 ms 7160 KB Output is correct
13 Correct 154 ms 7144 KB Output is correct
14 Correct 156 ms 7320 KB Output is correct
15 Correct 175 ms 7232 KB Output is correct
16 Correct 29 ms 3908 KB Output is correct
17 Correct 32 ms 3984 KB Output is correct
18 Correct 33 ms 3920 KB Output is correct
19 Correct 31 ms 4012 KB Output is correct
20 Correct 30 ms 4004 KB Output is correct
21 Incorrect 104 ms 6856 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 6 ms 1620 KB Output is correct
2 Correct 7 ms 1720 KB Output is correct
3 Correct 7 ms 1620 KB Output is correct
4 Correct 7 ms 1620 KB Output is correct
5 Correct 7 ms 1724 KB Output is correct
6 Correct 7 ms 1716 KB Output is correct
7 Correct 7 ms 1620 KB Output is correct
8 Correct 8 ms 1620 KB Output is correct
9 Correct 7 ms 1620 KB Output is correct
10 Correct 8 ms 1748 KB Output is correct
11 Correct 8 ms 1620 KB Output is correct
12 Correct 7 ms 1620 KB Output is correct
13 Correct 7 ms 1720 KB Output is correct
14 Correct 7 ms 1620 KB Output is correct
15 Correct 7 ms 1712 KB Output is correct
16 Correct 4 ms 1364 KB Output is correct
17 Correct 4 ms 1364 KB Output is correct
18 Correct 4 ms 1364 KB Output is correct
19 Correct 4 ms 1364 KB Output is correct
20 Correct 4 ms 1236 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 7116 KB Output is correct
2 Correct 155 ms 7120 KB Output is correct
3 Correct 154 ms 7220 KB Output is correct
4 Correct 154 ms 7204 KB Output is correct
5 Correct 156 ms 7200 KB Output is correct
6 Correct 154 ms 7116 KB Output is correct
7 Correct 158 ms 7132 KB Output is correct
8 Correct 158 ms 7204 KB Output is correct
9 Correct 159 ms 7176 KB Output is correct
10 Correct 165 ms 7112 KB Output is correct
11 Correct 152 ms 7204 KB Output is correct
12 Correct 155 ms 7160 KB Output is correct
13 Correct 154 ms 7144 KB Output is correct
14 Correct 156 ms 7320 KB Output is correct
15 Correct 175 ms 7232 KB Output is correct
16 Correct 29 ms 3908 KB Output is correct
17 Correct 32 ms 3984 KB Output is correct
18 Correct 33 ms 3920 KB Output is correct
19 Correct 31 ms 4012 KB Output is correct
20 Correct 30 ms 4004 KB Output is correct
21 Incorrect 104 ms 6856 KB Output isn't correct
22 Halted 0 ms 0 KB -