Submission #499777

#TimeUsernameProblemLanguageResultExecution timeMemory
499777StickfishBoat (APIO16_boat)C++17
9 / 100
1737 ms12380 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; const ll MOD = 1000000007; const int MAXN = 502; ll fact[MAXN * 2]; ll rfact[MAXN * 2]; ll pw(ll a, ll m) { if (!m) return 1; a %= MOD; if (m % 2) return (a * pw(a, m - 1)) % MOD; return pw(a * a, m / 2); } ll choose[MAXN * 2][MAXN]; ll dp[MAXN * 2][MAXN]; ll ndp[MAXN * 2][MAXN]; ll a[MAXN]; ll b[MAXN]; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); rfact[0] = fact[0] = 1; for (int i = 1; i < 2 * MAXN; ++i) { fact[i] = (fact[i - 1] * i) % MOD; rfact[i] = pw(fact[i], MOD - 2); } int n; cin >> n; vector<ll> cpr = {0}; vector<ll> sz; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; ++b[i]; cpr.push_back(a[i]); cpr.push_back(b[i]); } sort(cpr.begin(), cpr.end()); cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin()); int m = cpr.size(); for (int i = 0; i + 1 < m; ++i) { sz.push_back(cpr[i + 1] - cpr[i]); for (int k = 0; k <= i; ++k) { choose[i][k] = 1; for (int t = sz[i]; t > sz[i] - k; --t) { choose[i][k] = (choose[i][k] * t) % MOD; } choose[i][k] = (choose[i][k] * rfact[k]) % MOD; } } //printf("\n"); for (int i = 0; i < n; ++i) { a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin(); b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin(); } for (int i = 0; i < m; ++i) dp[i][0] = 1; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { for (int k = 0; k <= n; ++k) ndp[j][k] = 0; } for (int j = b[i] - 1; j >= a[i]; --j) { for (int k = 0; k <= n; ++k) { if (k) ndp[j][k] += dp[j][k - 1]; ndp[j][k] %= MOD; ndp[j + 1][0] += ndp[j][k] * choose[j][k]; ndp[j + 1][0] %= MOD; } } for (int j = 1; j < m; ++j) { ndp[j][0] += ndp[j - 1][0]; ndp[j][0] %= MOD; } for (int j = 0; j < m; ++j) { for (int k = 0; k <= n; ++k) { ndp[j][k] += dp[j][k]; ndp[j][k] %= MOD; } } for (int j = 0; j < m; ++j) { for (int k = 0; k <= n; ++k) dp[j][k] = ndp[j][k]; } //printf("---\n"); //for (int j = 0; j < m; ++j) { //for (int k = 0; k <= n; ++k) //printf("%Ld ", dp[j][k]); //printf("\n"); //} } cout << dp[m - 1][0] - 1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...