제출 #667180

#제출 시각아이디문제언어결과실행 시간메모리
667180KahouKangaroo (CEOI16_kangaroo)C++14
51 / 100
125 ms139672 KiB
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

int mod = 1e9 + 7;
int add(int a, int b) {
    a += b;
    if (a < 0) a += mod;
    if (a >= mod) a -= mod;
    return a;
}
int mul(int a, int b) {
    return 1ll*a*b%mod;
}

const int N = 205;
int n, cs, cf;
int dp[N][N][2][N];
int ps[N][N][2][N];

void solve() {
    cin >> n >> cs >> cf;
    dp[2][1][0][2] = dp[2][2][1][1] = 1;
    for (int f=1; f <= 2; f++) {
        for (int m = 0; m < 2; m++) {
            for (int s = 1; s <= 2; s++) {
                ps[2][f][m][s] = add(ps[2][f][m][s-1], dp[2][f][m][s]);
            }
        }
    }
    for (int x = 3; x <= n; x++) {
        for (int f = 1; f <= x; f++) {
            for (int s = 1; s <= x; s++) {
                ps[x][f][0][s] = ps[x][f][0][s-1];
                ps[x][f][1][s] = ps[x][f][1][s-1];
                if (s == f) continue;
                bool flg = f>s;
                dp[x][f][0][s] = ps[x-1][f-flg][1][s-1];
                dp[x][f][1][s] = add(ps[x-1][f-flg][0][x-1], -ps[x-1][f-flg][0][s-1]);
                ps[x][f][0][s] = add(ps[x][f][0][s-1], dp[x][f][0][s]);
                ps[x][f][1][s] = add(ps[x][f][1][s-1], dp[x][f][1][s]);
            }
        }
    }
    cout << add(dp[n][cf][0][cs], dp[n][cf][1][cs]) << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    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...