Submission #657171

#	Time	Username	Problem	Language	Result	Execution time	Memory
657171		Nhoksocqt1	Kangaroo (CEOI16_kangaroo)	C++17	0 / 100	1 ms	340 KiB

kangaroo

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

#define inf 0x3f3f3f3f
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define N 2002
#define modl 1000000007
typedef long long ll;
typedef pair<int, int> ii;

int dp[N][N], n, cs, cf;

inline void add(int &a, const int &b) {
    if((a += b) >= modl)
        a -= modl;
}

void process(void) {
    cin >> n >> cs >> cf;

    dp[0][0] = 1;
    for (int i = 0; i < n - 1; ++i) {
        for (int group = 0; group <= i; ++group) {
            if(!dp[i][group])
                continue;

            if(i + 1 == cs) {
                add(dp[i + 1][group], dp[i][group]);
                if(group > 0) {
                    add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                }
            } else
                if(i + 1 == cf) {
                    add(dp[i + 1][group], dp[i][group]);
                    if(group > 0) {
                        add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                    }
                } else {

                    add(dp[i + 1][group + 1], dp[i][group]);
                    if(group > 0) {
                        if(i + 1 >= cs) {
                            add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                        }

                        if(i + 1 >= cf) {
                            add(dp[i + 1][group - 1], 1LL * group * dp[i][group] % modl);
                        }

                        add(dp[i + 1][group], 1LL * group * dp[i][group] % modl);
                        add(dp[i + 1][group - 1], 1LL * dp[i][group] * group * (group - 1) / 2 % modl);
                    }
                }
        }
    }

    cout << dp[n - 1][0];
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

   // freopen("main.inp", "r", stdin);
  //  freopen("main.out", "w", stdout);

    process();
    return 0;
}

Compilation message (stderr)

kangaroo.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
kangaroo.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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