Submission #422206

#	Time	Username	Problem	Language	Result	Execution time	Memory
422206		julian33	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	1 ms	332 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

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

const int mxN=2e3+5,mod=1e9+7;

ll dp[mxN][mxN][2],pref[mxN][mxN],suff[mxN][mxN];

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    int n,s,f; cin>>n>>s>>f;
    dp[s][1][0]=dp[s][1][1]=1;
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n && j>1;i++){
            if(i==s)
                continue;
            dp[i][j][1]=(pref[i-1][j-1]-dp[i][max(0,j-2)][1]+mod)%mod;
            dp[i][j][0]=(suff[i+1][j-1]-dp[i][max(0,j-2)][0]+mod)%mod;
        }
        for(int i=1;i<=n;i++)
            pref[i][j]=(pref[i-1][j]+dp[i][j][0])%mod;
        for(int i=n;i>=1;i--)
            suff[i][j]=(suff[i+1][j]+dp[i][j][1])%mod;
        // for(int i=1;i<=n;i++){
        //     cout<<dp[i][j][0]<<","<<dp[i][j][1]<<" ";
        // }
        // cout<<"\n";
    }
    cout<<(dp[f][n][0]+dp[f][n][1])%mod<<"\n";
}

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