Submission #1078349

#TimeUsernameProblemLanguageResultExecution timeMemory
1078349underwaterkillerwhaleBoat (APIO16_boat)C++17
9 / 100
362 ms6996 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 5e2 + 7; const int Mod = 1e9 + 7; const int INF = 1e9; const ll BASE = 137; const int szBL = 320; int n, m; pii a[N]; int dp[N][N * 2], f[N][N * 2], com[N * 2][N], combi[N][N]; inline void add (int &a, int b) { a = a + b; if (a >= Mod) a = a - Mod; } ll power (int n, int m) { if (m == 0) return 1; ll t = power (n, m >> 1); (t *= t) %= Mod; if (m & 1) (t *= n) %= Mod; return t; } bool cover (pii A, pii B) { return A.fs <= B.fs && A.se >= B.se; } void solution () { cin >> n; vector<pii> vec, seg = {MP(0, 0)}; rep (i, 1, n) { cin >> a[i].fs >> a[i].se; vec.pb({a[i].fs, 0}), vec.pb({a[i].se, 1}); } sort (ALL(vec)); vec.resize(unique(ALL(vec)) - vec.begin()); rep (i, 0, SZ(vec) - 2) { if (vec[i].se == vec[i + 1].se) { if (vec[i].se == 1) seg.pb({vec[i].fs + 1, vec[i + 1].fs}); else seg.pb({vec[i].fs, vec[i + 1].fs - 1}); } else if (vec[i].se == 0) seg.pb({vec[i].fs, vec[i + 1].fs}); } m = SZ(seg) - 1; rep (i, 0, m) { int Len = seg[i].se - seg[i].fs + 1; com[i][0] = 1; rep (j, 1, n + 1) { if (j > Len) com[i][j] = 0; else com[i][j] = 1LL * com[i][j - 1] * (Len - j + 1) % Mod * power (j, Mod - 2) % Mod; // cout << seg[i].fs <<","<<seg[i].se<<" "<<j<<" "<<com[i][j] <<"\n"; } } rep (i, 0, n) { rep (j, 0, i) { if (j == i || j == 0) combi[i][j] = 1; else combi[i][j] = (combi[i - 1][j - 1] + combi[i - 1][j]) % Mod; } } rep (i, 0, n) { rep (j, 0, m) { rep (k, 0, i) { add(f[i][j], 1LL * combi[i][k] * com[j][k + 1] % Mod); } } } rep (j, 0, m) dp[0][j] = 1; rep (i, 1, n) { dp[i][0] = 1; rep (j, 1, m) { dp[i][j] = dp[i][j - 1]; int num = 0; reb (k, i, 1) { if (cover(a[k], seg[j])) { add(dp[i][j], 1LL * dp[k - 1][j - 1] * f[num][j] % Mod); ++num; } } // cout << i <<" "<<seg[j].fs<<","<<seg[j].se<<": "<<dp[i][j] <<"\n"; } } cout << (dp[n][m] - 1 + Mod) % Mod <<"\n"; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +4 mình có muốn dùng mảng này không? 4 5 1 3 4 1 1 2 3 2 2 1 return->break */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...