Submission #322005

#	Time	Username	Problem	Language	Result	Execution time	Memory
322005		EndRay	Kangaroo (CEOI16_kangaroo)	C++17	6 / 100	1 ms	492 KiB

kangaroo

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2000+1, mod = 1e9+7;

int n, i, j;

map<int, map<int, ll>> mp[N];

ll A[] = {1, 2, 16, 272, 7936};

ll f(int n, int i, int j){
    if(j == 1)
        return n == 1;
    if(i == 1 && j == 2){
        if((n&1) == 0)
            return 0;
        return A[(n-2)/2];
    }
    if(mp[n].find(i) != mp[n].end() && mp[n][i].find(j) != mp[n][i].end())
        goto END;
    if(i == 1){
        if(n&1) mp[n][i][j] = f(n, 1, j-1) - f(n-1, 1, j-1);
        else mp[n][i][j] =  f(n, 1, j-1) + f(n-1, 1, j-1);
    }
    else if(i == 2)
        mp[n][i][j] = f(n, 1, j) + f(n-1, 1, j-1);
    else mp[n][i][j] = 2*f(n, i-1, j) - f(n, i-2, j) - f(n-2, i-2, j-2);
    mp[n][i][j] %= mod;
END:
    return mp[n][i][j];
}

int main(){
    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    cin >> n >> i >> j;
    cout << f(n, i, j);
}

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