이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for(int (i) = (a); (i) < (n); ++(i))
#define per(i, n, a) for(int (i) = (n) - 1; (i) >= (a); --(i))
#define trav(i, x) for(auto& (i) : (x))
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef double db;
mt19937 mrand(random_device{}());
const int INF = 0x3f3f3f3f;
const int OFF = 1 << 20;
const int MOD = (int)1e9 + 7;
const int N = 550;
int n;
pii q[N];
vector<int> comp;
ll dist[2 * N];
ll dp[N][2 * N];
ll binom[2 * N][N];
ll add(ll a, ll b) {
if(a + b >= MOD) return a + b - MOD;
return a + b;
}
void gen_pascal() {
binom[0][0] = 1;
rep(i, 1, SZ(comp)) {
binom[i][0] = 1;
rep(j, 1, i + 1)
binom[i][j] = add(binom[i - 1][j], binom[i - 1][j - 1]);
}
}
int main() {
scanf("%d", &n);
rep(i, 1, n + 1) {
scanf("%d%d", &q[i].X, &q[i].Y);
comp.pb(q[i].X); comp.pb(q[i].Y + 1);
}
sort(all(comp));
gen_pascal();
comp.erase(unique(all(comp)), comp.end());
rep(i, 1, n + 1) {
q[i].X = lower_bound(all(comp), q[i].X) - comp.begin() + 1;
q[i].Y = lower_bound(all(comp), q[i].Y + 1) - comp.begin();
}
rep(i, 1, SZ(comp)) dist[i] = comp[i] - comp[i - 1];
rep(j, 0, SZ(comp)) dp[0][j] = 1;
rep(i, 1, n + 1) { // fiksiramo prefix
dp[i][0] = 1;
rep(j, q[i].X, q[i].Y + 1) { // fiksiramo kraj
dp[i][j] = add(dp[i][j], (dp[i - 1][j - 1] * dist[j]) % MOD); // ako samo sebe uzimamo
//printf("dp[%d][%d] -> %d\n", i, j, dp[i][j]);
int cnt = 1;
per(k, i, 1) {
if(j >= q[k].X && j <= q[k].Y) {
dp[i][j] = add(dp[i][j], (dp[k - 1][j - 1] * binom[dist[j]][++cnt]) % MOD);
}
}
}
rep(j, 1, SZ(comp))
dp[i][j] = (dp[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) % MOD;
}
printf("%lld\n", ((ll)dp[n][SZ(comp) - 1] - 1 + MOD) % MOD);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
boat.cpp: In function 'int main()':
boat.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
boat.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &q[i].X, &q[i].Y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |