Submission #1181015

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181015		Alish	Boat (APIO16_boat)	C++20	100 / 100	471 ms	5328 KiB

boat

#include<bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 1234;
const ll mod=1e9+7;

ll power(ll a, ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}

ll inv[N];
ll dp[N][N];
ll L[N], R[N];
int n;

int main()
{
    fast_io
    for (int i=1; i<N; i++) inv[i]=power(i, mod-2);

    cin>>n;
    vector<ll> vec;
    for (int i=1; i<=n; i++) {
        cin>>L[i]>>R[i];
        R[i]++;
        vec.pb(L[i]);
        vec.pb(R[i]);
    }
    sort(all(vec));
    vec.resize(unique(all(vec))-vec.begin());

    for (int j=0; j<N; j++) dp[0][j]=1;

    for (int i=1; i<=n; i++){
        int tl=lower_bound(all(vec), L[i])-vec.begin();
        int tr=lower_bound(all(vec), R[i])-vec.begin();
        for (int j=1; j<vec.size(); j++){
            dp[i][j]=dp[i][j-1];
            if(j<=tl || j>tr) continue;
            int num=0;
            ll za=1;
            for (int pre=i-1; pre>=0; pre--){
                if(L[pre+1]<=vec[j-1] && vec[j]<=R[pre+1]){
                    num++;
                    za=za*(vec[j]-vec[j-1]+num-1)%mod*inv[num]%mod;
                }
                dp[i][j]=(dp[i][j]+dp[pre][j-1]*za%mod)%mod;
            }

        }
    }
    ll ans=0;
    int temp=vec.size();
    for (int i=1; i<=n; i++) ans=(ans+dp[i][temp-1])%mod;
    cout<<ans<<endl;
}

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