Submission #1048086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048086		HossamHero7	Boat (APIO16_boat)	C++14	100 / 100	1241 ms	4312 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int mod = 1e9 + 7;
int add(int a,int b){
    return (a + b >= mod ? a + b - mod : a + b);
}
int sub(int a,int b){
    return (a - b >= 0 ? a - b : a - b + mod);
}
int mult(ll a,ll b){
	return (a*b)%mod;
}
int power(int a,int b){
	if(b == 0) return 1;
	if(b == 1) return a;
	int r = power(a,b/2);
	if(b&1) return mult(mult(r,r),a);
	return mult(r,r);
}
int divide(int a,int b){
    return mult(a , power(b,mod-2));
}
int dp[1005][505];
void solve(){
    int n;
    cin>>n;
    vector<int> a(n),b(n);
    vector<int> v;
    for(int i=0;i<n;i++){
        cin>>a[i]>>b[i];
        v.push_back(a[i]);
        v.push_back(b[i]+1);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()) , v.end());
    int new_n = v.size();
    vector<vector<int>> idx(new_n+1);
    for(int i=0;i<n;i++){
        int l = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
        int r = upper_bound(v.begin(),v.end(),b[i]) - v.begin();
        for(int j=l;j<r;j++){
            idx[j].push_back(i+1);
        }
    }
    vector<int> inv(n+1);
    for(int i=1;i<=n;i++) inv[i] = divide(1,i);
    for(int i=1;i<=n;i++) dp[new_n][i] = 1;
    for(int j=new_n-1;j>=0;j--){
        int sz = idx[j].size();
        vector<vector<int>> dp2(sz+1,vector<int>(sz+1));
        for(int i=sz-1;i>=0;i--){
            for(int k=1;k<=sz;k++){
                if(k == 1) dp2[i][k] = add(dp2[i][k] , dp[j+1][idx[j][i]]);
                else dp2[i][k] = add(dp2[i][k] , dp2[i+1][k-1]);
                dp2[i][k] = add(dp2[i][k] , dp2[i+1][k]);
            }
        }
        for(int i=0;i<=n;i++){
            int gap = (j < new_n - 1 ? v[j+1] - v[j] : 0);
            sz = min(sz , gap);
            int x = 1;
            int st = upper_bound(idx[j].begin(),idx[j].end(),i) - idx[j].begin();
            dp[j][i] = dp[j+1][i];
            for(int k=1;k<=sz;k++){
                x = mult(x , gap-k+1);
                x = mult(x , inv[k]);
                dp[j][i] = add(dp[j][i],mult(dp2[st][k],x));
            }
        }
    }
    cout<<dp[0][0]<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42