Submission #1020789

#TimeUsernameProblemLanguageResultExecution timeMemory
1020789flappybirdBoat (APIO16_boat)C++14
0 / 100
1377 ms8276 KiB
#include <bits/stdc++.h> #include <cassert> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma") using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; #define MAX 510 #define MAXQ 101010 #define INF 1000000100 #define bb ' ' #define ln '\n' #define Ln '\n' #define MOD 1000000007 int A[MAX]; int B[MAX]; int sz[MAX]; ll C[MAX * 2][MAX]; ll dp[MAX][MAX * 2]; ll mpow(ll x, ll y = MOD - 2) { if (!y) return 1; ll res = mpow(x, y >> 1); res *= res; res %= MOD; if (y & 1) res = (res * x) % MOD; return res; } ll rev[MAX * 2]; signed main() { ios::sync_with_stdio(false), cin.tie(0); int N; cin >> N; int i, j, k; vector<int> v; for (i = 1; i <= N; i++) { cin >> A[i] >> B[i]; B[i]++; v.push_back(A[i]); v.push_back(B[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); for (i = 1; i <= N; i++) { A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin(); B[i] = lower_bound(v.begin(), v.end(), B[i]) - v.begin(); } for (i = 1; i <= N * 2; i++) rev[i] = mpow(i); int X = v.size() - 1; for (i = 0; i < X; i++) { sz[i] = v[i + 1] - v[i]; for (j = 1; j <= N; j++) { ll c1, c2; c1 = 1; c2 = sz[i]; C[i][j] += c1 * c2; C[i][j] %= MOD; for (k = 0; k < j - 2; k++) { if (k < j - 1) { c1 *= j - 1 - k; c1 %= MOD; c1 *= rev[k + 1]; c1 %= MOD; } c2 *= sz[i] - (k + 1); c2 %= MOD; c2 *= rev[k + 2]; c2 %= MOD; C[i][j] += c1 * c2; C[i][j] %= MOD; } } } for (i = 1; i <= N; i++) { int cnt = 1; if (A[i] == 0) { for (j = 1; j < i; j++) if (A[j] == 0) cnt++; dp[i][0] += C[0][cnt]; } for (j = 1; j < X; j++) { dp[i][j] = dp[i][j - 1]; if (B[i] <= j) continue; if (j < A[i]) continue; cnt = 1; for (k = i - 1; k >= 1; k--) { dp[i][j] += C[j][cnt] * dp[i - 1][j - 1]; dp[i][j] %= MOD; if (A[k] <= j && j < B[k]) cnt++; } dp[i][j] += C[j][cnt]; } } ll ans = 0; for (i = 1; i <= N; i++) ans = (ans + dp[i][X - 1]) % MOD; cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...