Submission #1216528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216528		Zoli9	Kangaroo (CEOI16_kangaroo)	C++20	100 / 100	66 ms	94536 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
ll MOD=1e9+7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N, S, F;
    cin>>N>>S>>F;
    if(F<S) swap(S, F);
    ll diff=N-F;
    vector<vector<ll>> A(N+1, vector<ll>(N+1));
    vector<vector<ll>> D(N+1, vector<ll>(N+1));
    vector<vector<ll>> H(N+1, vector<ll>(N+1));
    H[2][2]=1;
    ll lastsum=1;
    for(int n=3; n<=N; n++) {
        ll cursum=0;
        for(int j=2; j<=n; j++) {
            if(j==2) {
                if(n%2) H[n][j]=lastsum;
            }
            else {
                if(n%2) H[n][j]=(H[n][j-1]-H[n-1][j-1]+MOD)%MOD;
                else H[n][j]=(H[n][j-1]+H[n-1][j-1])%MOD;
            }
            cursum=(cursum+H[n][j])%MOD;
        }
        lastsum=cursum;
    }
    for(int i=1; i<=S; i++) {
        for(int j=i+1; j<=F; j++) {
            if(i==1) {
                A[i][j]=H[j+diff][j];
            } else {
                A[i][j]=(A[i-1][j]-D[i-1][j-1]+MOD)%MOD;
                D[i][j]=(D[i-1][j]+A[i-1][j-1])%MOD;
            }
        }
    }
    cout<<(A[S][F]+D[S][F])%MOD<<'\n';
    return 0;
}

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