Submission #1213633

#TimeUsernameProblemLanguageResultExecution timeMemory
1213633loomBoat (APIO16_boat)C++20
100 / 100
1058 ms8444 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define inf 5e18 #define nl '\n' const int mod = 1e9+7; int exp(int a, int b = mod-2){ int p = 1; while(b > 0){ if(b % 2) p = p * a % mod; a = a * a % mod; b /= 2; } return p; } const int N = 2005; int dp[N][N]; inline void solve(){ int n; cin>>n; vector<pair<int,int>> ab(n+1), lr; map<int,int> mp; for(int i=1; i<=n; i++){ int a, b; cin>>a>>b; ab[i] = {a, b}; mp[a]++; mp[b]++; } int prev = -1; lr.push_back({0, 0}); for(auto [x, c] : mp){ if(prev != -1 and prev+1 <= x-1) lr.push_back({prev+1, x-1}); lr.push_back({x, x}); prev = x; } int m = lr.size()-1; for(int i=0; i<=m; i++) dp[0][i] = 1; int fact[n+1], inv[n+1]; fact[0] = inv[0] = 1; for(int i=1; i<=n; i++) fact[i] = fact[i-1] * i % mod, inv[i] = exp(fact[i]); for(int i=1; i<=n; i++){ auto [a, b] = ab[i]; dp[i][0] = 1; for(int j=1; j<=m; j++){ auto [l, r] = lr[j]; int len = r-l+1; dp[i][j] = dp[i][j-1]; int cnt = 0, p = 1; for(int k=i; k>0; k--){ auto [a, b] = ab[k]; if(l < a or r > b) continue; cnt++; p = p * (len + cnt - 1) % mod; dp[i][j] += p * inv[cnt] % mod * dp[k-1][j-1]; dp[i][j] %= mod; } } } cout<<(dp[n][m]-1+mod) % mod<<nl; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL); int t = 1; //cin>>t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...