제출 #527811

#제출 시각아이디문제언어결과실행 시간메모리
527811Monarchuwu캥거루 (CEOI16_kangaroo)C++17
0 / 100
1 ms332 KiB
/** * Problem: CEOI16_kangaroo - Kangaroo * Link: https://oj.uz/problem/view/CEOI16_kangaroo * Tags: DP CC **/ #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N = 2000 + 3, mod = 1e9 + 7; int n, cs, cf; #define add(a, b) (a += b) %= mod ll dp[N][N]; int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> n >> cs >> cf; if (cs > cf) cs = n - cs + 1, cf = n - cf + 1; dp[1][1] = 1; for (int i = 2; i <= n; ++i) for (int j = 1; j < i; ++j) if (dp[i - 1][j]) { if (cs == i) { add(dp[i][j + 1], dp[i - 1][j]); // nhảy sang phải add(dp[i][j + 0], dp[i - 1][j]); // nhảy sang trái continue; } if (cf == i) { add(dp[i][j + 1], dp[i - 1][j]); // đến từ phải add(dp[i][j + 0], dp[i - 1][j]); // đến từ trái add(dp[i][j - 1], dp[i - 1][j]); // merge với cs continue; } add(dp[i][j + 1], dp[i - 1][j] * (j - (cs < i) - (cf < i) + 1)); add(dp[i][j - 1], dp[i - 1][j] * (j - 1)); } cout << dp[n][1] << '\n'; } /** /\_/\ * (= ._.) * / >0 \>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...