제출 #858872

#제출 시각아이디문제언어결과실행 시간메모리
858872Tenis0206캥거루 (CEOI16_kangaroo)C++11
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; const int nmax = 2000; const int Mod = 1e9 + 7; int n,cs,cf; long long dp[nmax + 5][nmax + 5]; int main() { ios::sync_with_stdio(false); cin.tie(0); #ifdef home freopen("nr.in","r",stdin); freopen("nr.out","w",stdout); #endif // home cin>>n>>cs>>cf; if(cs > cf) { swap(cs,cf); } dp[0][0] = 1; for(int i=0; i<n; i++) { for(int nrg=0; nrg<=i; nrg++) { int val = i + 1; /// creez grup nou if(val == cs) { dp[i + 1][nrg + 1] += dp[i][nrg]; dp[i + 1][nrg + 1] %= Mod; } else if(val == cf) { dp[i + 1][nrg + 1] += dp[i][nrg]; dp[i + 1][nrg + 1] %= Mod; } else { if(val < cs) { dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * (nrg + 1) % Mod; dp[i + 1][nrg + 1] %= Mod; } else if(val < cf) { dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * nrg % Mod; dp[i + 1][nrg + 1] %= Mod; } else { dp[i + 1][nrg + 1] += 1LL * dp[i][nrg] * (nrg - 1) % Mod; dp[i + 1][nrg + 1] %= Mod; } } /// unesc doua grupuri existente if(val != cs && val != cf && nrg > 1) { dp[i + 1][nrg - 1] += 1LL * dp[i][nrg] * (nrg - 1) % Mod; dp[i + 1][nrg - 1] %= Mod; } /// adaug la inceput if(val <= cs && nrg > 0) { dp[i + 1][nrg] += dp[i][nrg]; dp[i + 1][nrg] %= Mod; } /// adaug la final if(val != cs && val <= cf && nrg > 0) { dp[i + 1][nrg] += dp[i][nrg]; dp[i + 1][nrg] %= Mod; } } } cout<<dp[n][1]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...