Submission #792677

#	Time	Username	Problem	Language	Result	Execution time	Memory
792677		RecursiveCo	Kangaroo (CEOI16_kangaroo)	C++14	36 / 100	2077 ms	435612 KiB

kangaroo

// CF template, version 3.0

#include <bits/stdc++.h>

using namespace std;

#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}

#define int long long int

int mod = 1e9 + 7;

signed main() {
    improvePerformance;
    get(n);
    get(a);
    get(b);
    a--;
    b--;
    vector<vector<vector<vector<int>>>> dp(n, vector<vector<vector<int>>>(n, vector<vector<int>>(n, vector<int>(2, 0))));
    // dp[c][i][j][0]: left
    // dp[c][i][j][1]: right
    dp[1][0][1][0] = 0;
    dp[1][0][1][1] = 1;
    dp[1][1][0][0] = 1;
    dp[1][1][0][1] = 0;
    for (int c = 2; c < n; c++) {
        forto(c + 1, i) {
            forto(c + 1, j) {
                if (i == j) continue;
                // going left.
                int left = 0;
                forto(i, k) {
                    int add;
                    if (i < j) {
                        add = dp[c - 1][k][j - 1][1];
                    } else {
                        add = dp[c - 1][k][j][1];
                    }
                    left = (left + add) % mod;
                }
                dp[c][i][j][0] = left;
                int right = 0;
                for (int k = i + 1; k <= c; k++) {
                    int add;
                    if (i < j) {
                        add = dp[c - 1][k - 1][j - 1][0];
                    } else {
                        add = dp[c - 1][k - 1][j][0];
                    }
                    right = (right + add) % mod;
                }
                dp[c][i][j][1] = right;
            }
        }
    }
    out((dp[n - 1][a][b][0] + dp[n - 1][a][b][1]) % mod);
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
kangaroo.cpp:24:5: note: in expansion of macro 'get'
   24 |     get(n);
      |     ^~~
kangaroo.cpp:10:23: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
kangaroo.cpp:25:5: note: in expansion of macro 'get'
   25 |     get(a);
      |     ^~~
kangaroo.cpp:10:23: warning: unnecessary parentheses in declaration of 'b' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
kangaroo.cpp:26:5: note: in expansion of macro 'get'
   26 |     get(b);
      |     ^~~
kangaroo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
kangaroo.cpp:37:9: note: in expansion of macro 'forto'
   37 |         forto(c + 1, i) {
      |         ^~~~~
kangaroo.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
kangaroo.cpp:38:13: note: in expansion of macro 'forto'
   38 |             forto(c + 1, j) {
      |             ^~~~~
kangaroo.cpp:15:35: warning: unnecessary parentheses in declaration of 'k' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
kangaroo.cpp:42:17: note: in expansion of macro 'forto'
   42 |                 forto(i, k) {
      |                 ^~~~~

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