제출 #351089

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351089		doowey	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	1790 ms	67680 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 202;
const int MOD = (int)1e9 + 7;
int dp[N][N][N][2];

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
}

int main(){
    fastIO;
    int n, a, b;
    cin >> n >> a >> b;
    a -- ;
    b -- ;
    dp[2][0][1][1]=1;
    dp[2][1][0][0]=1;
    for(int len = 3; len <= n; len ++ ){
        for(int x = 0; x < len; x ++ ){
            for(int y = 0; y < len; y ++ ){
                if(x == y) continue;
                // compute q = 1
                for(int nx = 0; nx < x; nx ++ ){
                    add(dp[len][x][y][0],dp[len-1][nx][y-(y>x)][1]);
                }
                for(int nx = x + 1; nx < len; nx ++ ){
                    add(dp[len][x][y][1],dp[len-1][nx-1][y-(y>x)][0]);
                }
            }
        }
    }
    cout << (dp[n][a][b][0] + dp[n][a][b][1]) % MOD;
}

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