Submission #39790

#TimeUsernameProblemLanguageResultExecution timeMemory
39790nickyrioBoat (APIO16_boat)C++14
9 / 100
367 ms58224 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i) #define FORD(i, a, b) for (int i = a, _b = b; i >= _b ; --i) #define REP(i, a) for (int i = 0, _a = a; i < a; ++i) #define pp pair<int, int> #define bit(S, i) (((S) >> i) & 1) #define next __next #define prev __prev #define N 1000100 #define NN 1111 #define taskname "" using namespace std; int n, a[NN], b[NN], len[NN]; vector<int> exist; long long rev[N]; const long long MOD = 1e9 + 7; long long c[NN][NN], dp[NN][NN], clen[NN][NN], g[NN][NN], total[NN][NN]; void Add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; FOR(i, 1, n) { cin >> a[i] >> b[i]; b[i]++; exist.push_back(a[i]); exist.push_back(b[i]); } sort(exist.begin(), exist.end()); exist.resize(unique(exist.begin(), exist.end()) - exist.begin()); rev[0] = rev[1] = 1; FOR(i, 2, n) rev[i] = (MOD - (MOD / i) * rev[MOD % i]) % MOD; int sz = exist.size() - 1; FOR(i, 0, n) c[0][i] = 1; FOR(i, 1, n) { c[i][i] = 1; FOR(j, i + 1, n) c[i][j] = (c[i - 1][j - 1] + c[i][j - 1]) % MOD; // c[k][n] } FOR(i, 1, sz) { len[i] = exist[i] - exist[i - 1]; clen[i][0] = 1; FOR(j, 1, n) { g[i][j] = 0; clen[i][j] = clen[i][j - 1] * (len[i] - j + 1) % MOD * rev[j] % MOD; } FOR(k, 2, n) { g[i][k] = 0; FOR(j, 2, min(k, len[i])) { Add(g[i][k], c[j - 2][k - 2] * clen[i][j] % MOD); } } } // FOR(i, 0, sz) total[0][i] = 1; FOR(i, 1, n) { FOR(j, 1, sz) { dp[i][j] = dp[i - 1][j];// Not choose i // Choose i if (a[i] <= exist[j - 1] && exist[j] <= b[i]) { int cnt = 0; FORD(k, i, 1) { if (a[k] <= exist[j - 1] && exist[j] <= b[k]) { cnt++; if (cnt == 1) { Add(dp[i][j], total[k - 1][j - 1] * 1ll * len[j] % MOD); } else Add(dp[i][j], total[k - 1][j - 1] * g[j][cnt] % MOD); } } } } total[i][0] = 1; FOR(j, 1, sz) total[i][j] = (dp[i][j] + total[i][j - 1]) % MOD; } cout << (total[n][sz] - 1 + MOD) % MOD; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...