제출 #1117693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1117693		vjudge1	캥거루 (CEOI16_kangaroo)	C++17	36 / 100	4 ms	2640 KiB

kangaroo

#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #define int long long
#define ll long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
const int oo = 1e9 + 9;
const int MAX = 40 + 5, LOGMAX = 20, B = 441, MOD = 1e9 + 7;

int n, cs, cf;
int dp[MAX][MAX][MAX][3];
int rec(int i, int prev, int finpos, int dir){
    if(i == n - 1) return (finpos == dir + 1);
    if(dp[i][prev][finpos][dir] != -1) return dp[i][prev][finpos][dir];
    int ans = 0;
    if(dir == 2 || dir == 0){
        for(int k = 1; k < prev; k++){
            if(k == finpos) continue;
            ans += rec(i + 1, k, finpos - (prev < finpos), 1);
            ans %= MOD;
        }
    }
    if(dir == 2 || dir == 1){
        for(int k = prev + 1; k <= n - i + 1; k++){
            if(k == finpos) continue;
            ans += rec(i + 1, k - 1, finpos - (prev < finpos), 0);
            ans %= MOD;
        }
    }
    return dp[i][prev][finpos][dir] = ans;
}

void solve(){
    cin >> n >> cs >> cf;
    memset(dp, -1, sizeof(dp));
    int ans = rec(1, cs, cf, 2);
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
}

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