Submission #792722

#	Time	Username	Problem	Language	Result	Execution time	Memory
792722		RecursiveCo	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	2066 ms	71508 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<int>>> dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
    vector<vector<vector<int>>> newdp(n, vector<vector<int>>(n, vector<int>(2, 0)));
    vector<vector<vector<int>>> oldpref(n, vector<vector<int>>(n, vector<int>(2, 0)));
    // dp[j][i][0]: left
    // dp[j][i][1]: right
    dp[1][0][0] = 0;
    dp[1][0][1] = 1;
    dp[0][1][0] = 1;
    dp[0][1][1] = 0;
    for (int c = 2; c < n; c++) {
        forto(c, j) {
            forto(c, i) {
                forto(2, d) {
                    if (i == 0) oldpref[j][i][d] = dp[j][i][d];
                    else oldpref[j][i][d] = (oldpref[j][i - 1][d] + dp[j][i][d]) % mod;
                }
            }
        }
        forto(c + 1, i) {
            forto(c + 1, j) {
                if (i == j) continue;
                // going left.
                int left;
                if (i < j) left = i? oldpref[j - 1][i - 1][1]: 0;
                else left = i? oldpref[j][i - 1][1]: 0;
                newdp[j][i][0] = left;
                int right;
                if (i < j) right = (oldpref[j - 1][c - 1][0] + mod - (i? oldpref[j - 1][i - 1][0]: 0)) % mod;
                else right = (oldpref[j][c - 1][0] + mod - (i? oldpref[j][i - 1][0]: 0)) % mod;
                newdp[j][i][1] = right;
            }
        }
        swap(dp, newdp);
    }
    out((dp[b][a][0] + dp[b][a][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 'j' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
kangaroo.cpp:39:9: note: in expansion of macro 'forto'
   39 |         forto(c, j) {
      |         ^~~~~
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:40:13: note: in expansion of macro 'forto'
   40 |             forto(c, i) {
      |             ^~~~~
kangaroo.cpp:15:35: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
kangaroo.cpp:41:17: note: in expansion of macro 'forto'
   41 |                 forto(2, d) {
      |                 ^~~~~
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:47:9: note: in expansion of macro 'forto'
   47 |         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:48:13: note: in expansion of macro 'forto'
   48 |             forto(c + 1, j) {
      |             ^~~~~

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