Submission #493880

#TimeUsernameProblemLanguageResultExecution timeMemory
493880KhoaHoBoat (APIO16_boat)C++11
9 / 100
50 ms1356 KiB
/// KoJa #include <bits/stdc++.h> using namespace std; #define task "DUT03TEAMS" #define pb push_back #define SZ(a) (a).begin(), (a).end() #define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End) #define BIT(a) (1LL << (a)) #define vec vector #define fi first #define se second typedef long long ll; typedef pair<int, int> ii; template <class T> inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); } template <class T> inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); } void init() { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } void fastio() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); } const int N = 505; const int mod = int(1e9) + 7; void add(int &a, const int &b) { a += b; if (a >= mod) a -= mod; } const ll INF = 1e18; int n, mem1[N][N]; ii a[N]; int backtrack1(int i, int x) { if (i == n + 1) { if (x != -1) return 1; return 0; } int &res = mem1[i][x]; if (res != -1) return res; res = 0; add(res, backtrack1(i + 1, x)); if (a[i].fi > x) add(res, backtrack1(i + 1, a[i].fi)); return res; } int res = 0, dp[N][N], pref[N + 10], fact[N], ifact[N]; int Pow(int x, int y) { int res = 1; while (y) { if (y & 1) res = 1LL * res * x % mod; x %= mod; x = 1LL * x * x % mod; y /= 2; } return res; } int main() { fastio(); //init(); cin >> n; bool sub1 = (n <= 500); for (int i = 1; i <= n; i++) { cin >> a[i].fi >> a[i].se; sub1 &= (a[i].fi == a[i].se); } fact[0] = 1; for (int i = 1; i < N; i++) fact[i] = 1LL * fact[i - 1] * i % mod; ifact[N - 1] = Pow(fact[N - 1], mod - 2); for (int i = N - 1; i >= 1; i--) ifact[i - 1] = 1LL * ifact[i] * i % mod; vec<int> val; if (sub1) { for (int i = 1; i <= n; i++) val.pb(a[i].fi); sort(SZ(val)); val.erase(unique(SZ(val)), val.end()); for (int i = 1; i <= n; i++) a[i].fi = lower_bound(SZ(val), a[i].fi) - val.begin() + 1; memset(mem1, -1, sizeof(mem1)); return cout << backtrack1(1, -1), 0; } for (int i = 1; i <= n; i++) { val.pb(a[i].fi); val.pb(a[i].se + 1); } sort(SZ(val)); val.erase(unique(SZ(val)), val.end()); for (int i = 1; i <= n; i++) a[i] = ii(lower_bound(SZ(val), a[i].fi) - val.begin() + 1, lower_bound(SZ(val), a[i].se) - val.begin() + 1); for (int i = 0; i < N; i++) pref[i] = 1; dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = a[i].fi; j < a[i].se; j++) { int len = val[j + 1] - val[j]; for (int k = N - 1; k >= 2; k--) add(dp[j][k], 1LL * dp[j][k - 1] * (len - k + 1) % mod * ifact[k] % mod); add(dp[j][1], 1LL * pref[j - 1] * len % mod); } pref[0] = dp[0][0]; for (int j = 1; j < N; j++) { pref[j] = pref[j - 1]; for (int k = 0; k < N; k++) add(pref[j], dp[j][k]); } } cout << (pref[N - 1] + mod - 1) % mod; return 0; }

Compilation message (stderr)

boat.cpp: In function 'void init()':
boat.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...