이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |