Submission #108271

#TimeUsernameProblemLanguageResultExecution timeMemory
108271polyfishBoat (APIO16_boat)C++14
58 / 100
2052 ms23260 KiB
//Pantyhose(black) + glasses = infinity #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "boat" const int MAX_N = 1002; const int MOD = 1000000007; int n, l[MAX_N], r[MAX_N]; vector<pair<int, int> > seg; int64_t C1[MAX_N][MAX_N], C2[MAX_N][MAX_N]; int64_t inv[MAX_N], inv_fact[MAX_N], f[MAX_N][MAX_N], P[MAX_N][MAX_N]; void read_input() { cin >> n; for (int i=1; i<=n; ++i) cin >> l[i] >> r[i]; } void init() { vector<int> x; for (int i=1; i<=n; ++i) { x.push_back(l[i]); x.push_back(r[i]+1); } sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin()); seg.push_back({0, 0}); for (int i=0; i+1<x.size(); ++i) { seg.push_back({x[i], x[i+1]-1}); // cerr << seg.back().first << ' ' << seg.back().second << '\n'; } inv[1] = 1; inv_fact[0] = inv_fact[1] = 1; for (int i=2; i<=n; ++i) { inv[i] = MOD - MOD/i*inv[MOD%i]%MOD; inv_fact[i] = inv_fact[i-1] * inv[i] % MOD; } // debug(inv[2]*2%MOD); } int64_t comb(int n, int k) { if (n<0 || n<k) return 0; int64_t res = 1; for (int i=n-k+1; i<=n; ++i) res = res * i % MOD; return res * inv_fact[k] % MOD; } bool contain(int u, int v, int l, int r) { return (u<=l && r<=v); } void dp() { for (int i=1; i<seg.size(); ++i) { for (int j=1; j<=n; ++j) C2[i][j] = comb(seg[i].second - seg[i].first + 1, j); } for (int i=0; i<=n; ++i) C1[i][i] = C1[i][0] = 1; for (int i=1; i<=n; ++i) { for (int j=1; j<i; ++j) C1[i][j] = (C1[i-1][j] + C1[i-1][j-1]) % MOD; } for (int i=1; i<seg.size(); ++i) { for (int k=1; k<=n; ++k) { for (int j=1; j<=k; ++j) P[i][k] = (P[i][k] + C2[i][j] * C1[k-1][j-1]) % MOD; } } // debug(P[1][1]); for (int i=0; i<seg.size(); ++i) f[0][i] = 1; for (int i=0; i<=n; ++i) f[i][0] = 1; int64_t res = 0; for (int i=1; i<=n; ++i) { for (int j=1; j<seg.size(); ++j) { f[i][j] = f[i][j-1]; int cnt = 0; for (int k=i; k>=1; --k) { if (contain(l[k], r[k], seg[j].first, seg[j].second)) { ++cnt; // if (i==3 && j==1 && k==1) // debug(tmp); f[i][j] = (f[i][j] + f[k-1][j-1] * P[j][cnt]) % MOD; } } } } // debug(f[3][0]); cout << (f[n][seg.size()-1] - 1 + MOD) % MOD; } int main() { #ifdef GLASSES_GIRL freopen(FILE_NAME".in", "r", stdin); freopen(FILE_NAME".out", "w", stdout); #endif ios::sync_with_stdio(0); cin.tie(0); read_input(); init(); dp(); }

Compilation message (stderr)

boat.cpp: In function 'void init()':
boat.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i+1<x.size(); ++i) {
                ~~~^~~~~~~~~
boat.cpp: In function 'void dp()':
boat.cpp:70:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<seg.size(); ++i) {
                ~^~~~~~~~~~~
boat.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<seg.size(); ++i)
                ~^~~~~~~~~~~
boat.cpp:98:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<seg.size(); ++j) {
                 ~^~~~~~~~~~~
boat.cpp:95:10: warning: unused variable 'res' [-Wunused-variable]
  int64_t res = 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...