이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
ll dp[205][205][205][2];
bool was[205][205][205][2];
ll solve(int n, int s, int f, int w) {
if(s == f) {
return (n == 1 ? 1 : 0);
}
if(n == 2 && ((s < f && w == 1) || (s > f && w == 0))) {
return 1;
} else if(n == 2) {
return 0;
}
if(was[n][s][f][w]) {
return dp[n][s][f][w];
}
was[n][s][f][w] = true;
ll ans = 0;
for(int i = 1; i <= n; i++) {
if(i == s) {
continue;
}
if(w == 1 && i < s) {
continue;
}
if(w == 0 && i > s) {
continue;
}
ans+= solve(n-1,(i < s ? i : i-1),(f < s ? f : f-1),1-w);
}
ans = ans%MOD;
// cout << n << " " << s << " " << f << " " << w << " " << ans << endl;
dp[n][s][f][w] = ans;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n,s,f;
cin >> n >> s >> f;
cout << (solve(n,s,f,0)+solve(n,s,f,1))%MOD;
return 0;
}
| # | 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... |