Submission #1295346

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295346		ElayV13	Kangaroo (CEOI16_kangaroo)	C++20	36 / 100	4 ms	1084 KiB

kangaroo

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

#define int long long
const int mod = (1e9 + 7) , INF = (1e18) , N = (2e5 + 5) , LOG = (20);

int n , cs , cf;
int dp[41][41][41][2];

int add(int a , int b){
          return (a + b) % mod;
}

signed main(){
          cin >> n >> cs >> cf;
          dp[2][1][2][0] = 1;
          dp[2][2][1][1] = 1;
          for(int len = 3;len <= n;len++)
          {
                    for(int s = 1;s <= len;s++)
                    {
                              for(int f = 1;f <= len;f++)
                              {
                                        if(f == s) continue;
                                        for(int k = s;k < len;k++)
                                        {
                                                  dp[len][s][f][0] = add(dp[len][s][f][0] , dp[len - 1][k][f - ((f > s) ? 1 : 0)][1]);
                                        }
                                        for(int k = 1;k < s;k++)
                                        {
                                                  dp[len][s][f][1] = add(dp[len][s][f][1] , dp[len - 1][k][f - ((f > s) ? 1 : 0)][0]);
                                        }
                              }
                    }
          }
          cout << add(dp[n][cs][cf][0] , dp[n][cs][cf][1]) << "\n";
}

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