Submission #625378

#	Time	Username	Problem	Language	Result	Execution time	Memory
625378		jasmin	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	236 ms	110584 KiB

kangaroo

#include<bits/stdc++.h>
using namespace std;
#define int long long

int32_t n, start, ende;

const int mod=1e9+7;
vector<vector<vector<int32_t> > > mem;
int32_t dp(int i, int left, int right){
    if(left<0 || right<0) return 0;
    if(left>n || right>n) return 0;
    
    int r=(right-left)+1;
    if(mem[i][left][r]!=-1) return mem[i][left][r];
    
    if(i==start){
        mem[i][left][r]=((dp(i-1, left+1, right)*(left+1))%mod + dp(i-1, left, right-1))%mod;
        return mem[i][left][r];
    }
    else if(i==ende){
        mem[i][left][r]=((dp(i-1, left, right+1)*(right + (i==n)))%mod + dp(i-1, left-1, right))%mod;
        return mem[i][left][r];
    }
    else{
        int chose2=(((left+1)*(right+(i==n))))%mod;
        mem[i][left][r]=((dp(i-1, left+1, right+1)*chose2)%mod+ dp(i-1, left-1, right-1))%mod;
        return mem[i][left][r];
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> start >> ende;
    if(ende<start) swap(start, ende);

    mem.resize(n+1);
    vector<vector<int32_t> > p(1, vector<int32_t> (3, -1));
    for(int i=n; i>=0; i--){
        mem[i]=p;
        p.push_back(vector<int32_t> (3, -1));
    }
    for(int i=0; i<=n; i++){
        for(int j=0; j<3; j++){
            mem[0][i][j]=0;
        }
    }
    mem[0][0][1]=1;
    
    cout << dp(n, 0, 0) << "\n";
}

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