제출 #667180

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667180		Kahou	캥거루 (CEOI16_kangaroo)	C++14	51 / 100	125 ms	139672 KiB

kangaroo

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49