Submission #1197803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197803		aarb_.tomatexd	Boat (APIO16_boat)	C++20	100 / 100	204 ms	8740 KiB

boat

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back
const int mxN = 500, M = 1e9+7;
int n, a[mxN], b[mxN];
ll dp[mxN+1][2*mxN], c[2*mxN][mxN+1];
vector<int>pts;
inline ll modI(ll a, ll m){ return a<=1?a:(1-modI(m%a,a)*m)/a+m; }

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cin >> n;
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i], --a[i];
        pts.pb(a[i]); pts.pb(b[i]);
    }
    sort(pts.begin(), pts.end());
    pts.resize(unique(pts.begin(), pts.end())-pts.begin());
    for(int i=1;i<pts.size();i++){
        c[i][1] = pts[i]-pts[i-1];
        for(int j=2;j<=n;j++) c[i][j]=c[i][j-1]*(pts[i]-pts[i-1]+j-1)%M*modI(j,M)%M;
    }
    for(int i=0;i<pts.size();i++) dp[0][i]=1;
    for(int i=1;i<=n;i++){
        dp[i][0] = 1;
        for(int j=1;j<pts.size();j++){
            dp[i][j] = dp[i][j-1];
            for(int k=i,n2=0;k;k--){
                if(pts[j]>a[k-1]and pts[j]<=b[k-1]){
                    ++n2;
                    dp[i][j]+=dp[k-1][j-1]*c[j][n2]%M;
                }
            }
            dp[i][j]%=M;
        }
    }
    cout<<dp[n][pts.size()-1]-1<<endl;
}

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