Submission #46418

#TimeUsernameProblemLanguageResultExecution timeMemory
46418TransBoat (APIO16_boat)C++14
0 / 100
7 ms3832 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = (a); i < (b); i++) #define repd(i, a, b) for (int i = (a) - 1; i >= b; i--) #define pb push_back #define fi first #define se second typedef long long ll; const int mod = 1e9 + 7; const int maxn = 505; int n, a[maxn], b[maxn]; map<int, int> mm; ll dp[maxn][maxn * 2]; vector<ll> vi; ll power_mod(ll a, ll b) { ll res = 1; while (b) { if (b % 2) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int main() { cin >> n; mm[0]; rep(i, 0, n) { cin >> a[i] >> b[i]; mm[a[i] - 1]++; mm[b[i]]++; } int cnt = 0; for (auto it = mm.begin(); it != mm.end(); it++) { it->se = cnt++; vi.pb(it->fi); } ll ans = 0; rep(i, 0, n) { int hi = mm[b[i]] + 1; int lo = mm[a[i] - 1] + 1; dp[i][0] = 1; repd(k, hi, lo) { ll ways = (vi[k] - vi[k - 1]) * (i ? dp[i - 1][k - 1] : 1); ll range = vi[k] - vi[k - 1]; ll now = range; repd(j, i, 0) { if (b[j] < vi[k - 1] + 1 || a[j] > vi[k]) break; now = now * power_mod(i - j + 1, mod - 2) % mod; now = now * (range + i - j) % mod; ways += now * (j ? dp[j - 1][k - 1] : 1) % mod; ways %= mod; } // if (i == 1) cout << ways << endl; dp[i][k] = ways; } rep(k, 1, hi) { dp[i][k] = (dp[i][k] + dp[i][k - 1]) % mod; ans = dp[i][k]; } } // cout << dp[1][2] << endl; cout << ans; 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...