oj.uz

Submission #487427

# Submission time Handle Problem Language Result Execution time Memory
487427 2021-11-15T13:21:10 Z leaked Boat (APIO16_boat) C++14
9 / 100
 659 ms 4424 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define pb push_back
#define vec vector
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define fast_iati ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
typedef long long ll;
typedef pair<int,int> pii;
const int M=1e9+7;
const int N=5e2+10;
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int binpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
int inv[N];
int gi(int x){
    if(!inv[x]) inv[x]=binpow(x,M-2);
    return inv[x];
}
int C(int k,int n){
    if(k>n) return 0;
    int ans=1;
    for(int i=n-k+1;i<=n;i++) ans=mult(ans,i);
    for(int i=1;i<=k;i++) ans=mult(ans,gi(i));
    return ans;
}
signed main(){
    fast_iati;
    int n;
    cin>>n;
    vec<int>a(n),b(n);
    vec<int> kek;
    for(int i=0;i<n;i++) cin>>a[i]>>b[i],kek.pb(a[i]-1),kek.pb(b[i]);
    kek.pb(0);sort(all(kek));kek.erase(unique(all(kek)),kek.end());
    vec<vec<int>>dp(n+1,vec<int>(sz(kek)+1,0));
    vec<int>ways(sz(kek));
    vec<vec<int>>col(sz(kek),vec<int>(n+1,0));
    for(int i=1;i<sz(kek);i++){
        ways[i]=kek[i]-kek[i-1];
        for(int j=1;j<=n;j++){
            col[i][j]=C(j,ways[i]);
//            cout<<"HELLO "<<i<<' '<<ways[i]<<' '<<j<<' '<<col[i][j]<<endl;
        }
    }
    for(int j=0;j<sz(kek);j++) dp[0][j]=1;
    for(int i=0;i<n;i++){
        a[i]=lower_bound(all(kek),a[i]-1)-kek.begin()+1;
        b[i]=lower_bound(all(kek),b[i])-kek.begin();
    }
    for(int i=0;i<n;i++){
        for(int j=a[i];j<=b[i];j++){
            for(int k=i;k>=0;k--){
                if(a[k]>j || b[k]<j) break;
//                cout<<"DEBUG "<<j<<' '<<k<<' '<<i<<' '<<col[j][i-k+1]<<endl;
                add(dp[i+1][j],mult(col[j][i-k+1],dp[k][j-1]));
            }
        }
//        add(dp[i+1][0],1);
//        for(int j=1;j<sz(kek);j++) add(dp[i+1][j],dp[i+1][j-1]);
//        cerr<<"HELLO "<<endl;
//        cout<<sz(dp[i+1])<<endl;
//        for(int j=0;j<sz(kek);j++){
//            cout<<"DP i+1 j "<<dp[i+1][j]<<' '<<i+1<<' '<<j<<endl;
//        }
//        cout<<endl;
        for(int j=1;j<sz(kek);j++) add(dp[i+1][j],dp[i+1][j-1]);
//        cout<<dp[i+1][j]<<endl;
        for(int j=0;j<sz(kek);j++){
//            add(dp[i+1][j],dp[i][j]);
//            cout<<"WTF "<<dp[i][j]<<' '<<dp[i+1][j]<<endl;
            add(dp[i+1][j],dp[i][j]);

        }
    }
//    add(ans,-1);
    int ans=dp[n][sz(kek)-1];
    add(ans,-1);
//    for(int j=0;j<=sz(kek);j++) add(ans,dp[n][j]);
    cout<<ans;
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 4300 KB Output is correct
2 Correct 659 ms 4304 KB Output is correct
3 Correct 625 ms 4304 KB Output is correct
4 Correct 630 ms 4424 KB Output is correct
5 Correct 646 ms 4304 KB Output is correct
6 Correct 651 ms 4424 KB Output is correct
7 Correct 634 ms 4308 KB Output is correct
8 Correct 620 ms 4304 KB Output is correct
9 Correct 630 ms 4308 KB Output is correct
10 Correct 636 ms 4308 KB Output is correct
11 Correct 627 ms 4308 KB Output is correct
12 Correct 639 ms 4304 KB Output is correct
13 Correct 635 ms 4308 KB Output is correct
14 Correct 616 ms 4304 KB Output is correct
15 Correct 619 ms 4304 KB Output is correct
16 Correct 114 ms 1040 KB Output is correct
17 Correct 134 ms 1104 KB Output is correct
18 Correct 116 ms 1072 KB Output is correct
19 Correct 117 ms 1104 KB Output is correct
20 Correct 116 ms 1084 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 4300 KB Output is correct
2 Correct 659 ms 4304 KB Output is correct
3 Correct 625 ms 4304 KB Output is correct
4 Correct 630 ms 4424 KB Output is correct
5 Correct 646 ms 4304 KB Output is correct
6 Correct 651 ms 4424 KB Output is correct
7 Correct 634 ms 4308 KB Output is correct
8 Correct 620 ms 4304 KB Output is correct
9 Correct 630 ms 4308 KB Output is correct
10 Correct 636 ms 4308 KB Output is correct
11 Correct 627 ms 4308 KB Output is correct
12 Correct 639 ms 4304 KB Output is correct
13 Correct 635 ms 4308 KB Output is correct
14 Correct 616 ms 4304 KB Output is correct
15 Correct 619 ms 4304 KB Output is correct
16 Correct 114 ms 1040 KB Output is correct
17 Correct 134 ms 1104 KB Output is correct
18 Correct 116 ms 1072 KB Output is correct
19 Correct 117 ms 1104 KB Output is correct
20 Correct 116 ms 1084 KB Output is correct
21 Incorrect 11 ms 3920 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 635 ms 4300 KB Output is correct
2 Correct 659 ms 4304 KB Output is correct
3 Correct 625 ms 4304 KB Output is correct
4 Correct 630 ms 4424 KB Output is correct
5 Correct 646 ms 4304 KB Output is correct
6 Correct 651 ms 4424 KB Output is correct
7 Correct 634 ms 4308 KB Output is correct
8 Correct 620 ms 4304 KB Output is correct
9 Correct 630 ms 4308 KB Output is correct
10 Correct 636 ms 4308 KB Output is correct
11 Correct 627 ms 4308 KB Output is correct
12 Correct 639 ms 4304 KB Output is correct
13 Correct 635 ms 4308 KB Output is correct
14 Correct 616 ms 4304 KB Output is correct
15 Correct 619 ms 4304 KB Output is correct
16 Correct 114 ms 1040 KB Output is correct
17 Correct 134 ms 1104 KB Output is correct
18 Correct 116 ms 1072 KB Output is correct
19 Correct 117 ms 1104 KB Output is correct
20 Correct 116 ms 1084 KB Output is correct
21 Incorrect 11 ms 3920 KB Output isn't correct
22 Halted 0 ms 0 KB -