제출 #839859

#제출 시각아이디문제언어결과실행 시간메모리
839859popovicirobertBoat (APIO16_boat)C++14
100 / 100
1603 ms12404 KiB
#include <bits/stdc++.h> using namespace std; constexpr int MOD = (int) 1e9 + 7; inline int logpow(int a, int b) { int answer = 1; while (b > 0) { if (b & 1) answer = (1LL * answer * a) % MOD; b >>= 1; a = (1LL * a * a) % MOD; } return answer; } inline void add(int& x, int y) { x += y; if (x >= MOD) x -= MOD; } constexpr int MAXN = 505; int dp[2][4 * MAXN + 1][MAXN + 1]; int sp[2][4 * MAXN + 1]; int main() { #ifdef HOME ifstream cin("input.in"); ofstream cout("output.out"); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int n; cin >> n; vector<int> a(n + 1), b(n + 1); vector<int> x; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; x.push_back(a[i]); x.push_back(b[i]); } sort(x.begin(), x.end()); x.resize(unique(x.begin(), x.end()) - x.begin()); vector<pair<int, int>> segs; segs.push_back({0, 0}); for (int i = 0; i < (int)x.size(); i++) { segs.push_back({x[i], x[i]}); if (i + 1 < (int)x.size() && x[i] + 1 <= x[i + 1] - 1) { segs.push_back({x[i] + 1, x[i + 1] - 1}); } } vector<vector<int>> comb(segs.size(), vector<int>(n + 1)); for (int i = 0; i < (int)segs.size(); i++) { auto s = segs[i]; int size = s.second - s.first + 1; int fact = 1, prod = 1; comb[i][0] = 1; for (int j = 1; j <= n; j++) { if (j > size) { comb[i][j] = 0; continue; } prod = (1LL * prod * (size - j + 1)) % MOD; fact = (1LL * fact * j) % MOD; comb[i][j] = (1LL * logpow(fact, MOD - 2) * prod) % MOD; } } // for (auto itr : segs) { // cerr << itr.first << " " << itr.second << " "; // } // cerr << "\n"; auto Comb = [&segs, &comb](int j, int k) { return segs[j].second - segs[j].first + 1 < k ? 0 : comb[j][k]; }; auto Calc = [&segs, &Comb](int i) { for (int j = 0; j < (int)segs.size(); j++) { for (int k = 1; k <= i + 1; k++) { int curr = dp[i & 1][j][k]; if (curr == 0) continue; sp[i & 1][j] = (sp[i & 1][j] + 1LL * Comb(j, k) * curr) % MOD; } } for (int j = 1; j < (int)segs.size(); j++) { add(sp[i & 1][j], sp[i & 1][j - 1]); } }; dp[0][0][1] = 1; Calc(0); for (int i = 1; i <= n; i++) { memset(sp[i & 1], 0, sizeof(sp[i & 1])); memset(dp[i & 1], 0, sizeof(dp[i & 1])); for (int j = 0; j < (int)segs.size(); j++) { for (int k = 1; k <= i; k++) { dp[i & 1][j][k] = dp[1 - i & 1][j][k]; } if (a[i] <= segs[j].first && segs[j].second <= b[i]) { add(dp[i & 1][j][1], sp[1 - i & 1][j - 1]); for (int k = 1; k <= i; k++) { add(dp[i & 1][j][k], dp[1 - i & 1][j][k - 1]); } } } // for (int j = 0; j < (int)segs.size(); j++) { // cerr << sp[1 - i & 1][j] << " "; // } // cerr << "\n"; // for (int j = 0; j < (int)segs.size(); j++) { // for (int k = 1; k <= i; k++) { // cerr << dp[i & 1][j][k] << " "; // } // cerr << "\n"; // } // cerr << "\n"; Calc(i); } cout << (sp[n & 1][(int)segs.size() - 1] + MOD - 1) % MOD; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:113:40: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  113 |                 dp[i & 1][j][k] = dp[1 - i & 1][j][k];
      |                                      ~~^~~
boat.cpp:116:43: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  116 |                 add(dp[i & 1][j][1], sp[1 - i & 1][j - 1]);
      |                                         ~~^~~
boat.cpp:118:47: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
  118 |                     add(dp[i & 1][j][k], dp[1 - i & 1][j][k - 1]);
      |                                             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...