제출 #499713

#제출 시각아이디문제언어결과실행 시간메모리
499713StickfishBoat (APIO16_boat)C++17
9 / 100
7 ms4236 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; const ll MOD = 1000000007; const int MAXN = 502; ll dp__[MAXN][MAXN * 2]; ll* dp_[MAXN]; ll** dp = dp_ + 1; ll a[MAXN]; ll b[MAXN]; signed main() { for (int i = 0; i < MAXN; ++i) dp_[i] = dp__[i] + 1; int n; cin >> n; vector<ll> cpr = {0}; vector<ll> sz; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; ++b[i]; cpr.push_back(a[i]); cpr.push_back(b[i]); } sort(cpr.begin(), cpr.end()); cpr.resize(unique(cpr.begin(), cpr.end()) - cpr.begin()); int m = cpr.size(); for (int i = 0; i + 1 < m; ++i) { sz.push_back(cpr[i + 1] - cpr[i]); } for (int i = 0; i < n; ++i) { a[i] = lower_bound(cpr.begin(), cpr.end(), a[i]) - cpr.begin(); b[i] = lower_bound(cpr.begin(), cpr.end(), b[i]) - cpr.begin(); } for (int i = 0; i < m; ++i) dp[-1][i] = 1; for (int i = 0; i < n; ++i) { for (int j = a[i]; j < b[i]; ++j) { dp[i][j] = (dp[i - 1][j - 1] * sz[j]) % MOD; } for (int j = 0; j < m; ++j) { dp[i][j] += dp[i][j - 1]; dp[i][j] %= MOD; } for (int j = 0; j < m; ++j) { dp[i][j] += dp[i - 1][j]; dp[i][j] %= MOD; } } //for (int i = 0; i < n; ++i) { //for (int j = 0; j < m; ++j) //cout << dp[i][j] << ' '; //cout << endl; //} cout << dp[n - 1][m - 1] - 1 << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...