| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 604980 | snasibov05 | Kangaroo (CEOI16_kangaroo) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int mxn = 2005;
const int m = 1e9 + 7;
int dp[mxn][mxn][mxn][2];
int pref[mxn][mxn][mxn][2];
int suf[mxn][mxn][mxn][2];
// dir : 0 -> left, 1 -> right;
void calc(int sz, int st, int fn, int dir){
if (dp[sz][st][fn][dir] != -1) return;
if (st == fn) {
if (sz == 1) dp[sz][st][fn][dir] = 1;
else dp[sz][st][fn][dir] = 0;
return;
}
dp[sz][st][fn][dir] = 0;
if (dir == 0){
for (int to = 1; to < st; ++to){
if (st < fn) {
calc(sz - 1, to, fn - 1, 1);
dp[sz][st][fn][dir] += dp[sz - 1][to][fn - 1][1];
dp[sz][st][fn][dir] %= m;
}
else {
calc(sz - 1, to, fn, 1);
dp[sz][st][fn][dir] += dp[sz - 1][to][fn][1];
dp[sz][st][fn][dir] %= m;
}
}
} else{
for (int to = st+1; to <= sz; ++to){
if (st < fn) {
calc(sz - 1, to - 1, fn - 1, 0);
dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn - 1][0];
dp[sz][st][fn][dir] %= m;
}
else {
calc(sz - 1, to - 1, fn, 0);
dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn][0];
dp[sz][st][fn][dir] %= m;
}
}
}
}
int main() {
int n, cs, cf; cin >> n >> cs >> cf;
dp[1][1][1][0] = dp[1][1][1][1] = 1;
pref[1][1][1][0] = pref[1][1][1][1] = 1;
suf[1][1][1][0] = suf[1][1][1][1] = 1;
for (int sz = 2; sz <= n; ++sz){
for (int fn = 1; fn <= sz; ++fn){
for (int st = 1; st <= sz; ++st){
if (st == fn) continue;
if (st < fn) {
dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn - 1][1];
dp[sz][st][fn][0] %= m;
} else{
dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn][1];
dp[sz][st][fn][0] %= m;
}
if (st < fn) {
dp[sz][st][fn][1] += suf[sz - 1][st][fn - 1][0];
dp[sz][st][fn][1] %= m;
} else{
dp[sz][st][fn][1] += suf[sz - 1][st][fn][0];
dp[sz][st][fn][1] %= m;
}
}
for (int st = 1; st <= sz; ++st) pref[sz][st][fn][1] = (pref[sz][st-1][fn][1] + dp[sz][st][fn][1]) % m;
for (int st = sz; st > 0; --st) suf[sz][st][fn][0] = (suf[sz][st+1][fn][0] + dp[sz][st][fn][0]) % m;
}
}
int ans = dp[n][cs][cf][0] + dp[n][cs][cf][1];
ans %= m;
cout << ans << "\n";
return 0;
}