Submission #236752

#	Time	Username	Problem	Language	Result	Execution time	Memory
236752		Sorting	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	50 ms	31736 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int k_N = 2000 + 3;
const int k_Mod = 1e9 + 7;

int n, cs, cf;
long long dp[k_N][k_N];

void fix(long long &x){
    x = (x >= k_Mod) ? (x - k_Mod) : x;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> cs >> cf;
    //cs--, cf--;
    if(cs > cf)
        swap(cs, cf);

    for(int pos = 0; pos <= n; ++pos){
        for(long long group = 0; group <= n; ++group){
            long long &answer = dp[pos][group];
            if(pos == 0){
                answer = (group == 1);
                continue;
            }

            answer = 0;

            if(pos > cf){
                answer = dp[pos - 1][group + 1];
                if(group >= 2){
                    answer += dp[pos - 1][group - 1] * group % k_Mod * (group - 1) % k_Mod;
                    fix(answer);
                }
            }
            else if(pos == cf){
                answer = dp[pos - 1][group + 1];
                answer += dp[pos - 1][group] * group % k_Mod;
                fix(answer);
            }
            else if(pos > cs){
                answer = dp[pos - 1][group + 1];
                if(group >= 2){
                    answer += dp[pos - 1][group - 1] * (group - 1) % k_Mod * (group - 1) % k_Mod;
                    fix(answer);
                }
            }
            else if(pos == cs){
                answer = dp[pos - 1][group + 1];
                if(pos != 1){
                    if(group)
                        answer += dp[pos - 1][group] * (group - 1) % k_Mod;
                }
                else
                    answer += dp[pos - 1][group] * group % k_Mod;
                fix(answer);
            }
            else if(pos < cs){
                answer = dp[pos - 1][group + 1];
                if(group >= 2){
                    if(pos == 1)
                        answer += dp[pos - 1][group - 1] * (((group * group % k_Mod - 3 * group + 3) % k_Mod + k_Mod) % k_Mod) % k_Mod;
                    else
                        answer += dp[pos - 1][group - 1] * (((group * group % k_Mod - 3 * group + 2) % k_Mod + k_Mod) % k_Mod) % k_Mod;
                    fix(answer);
                }
            }

            //cout << answer << " - " << pos << " " << group << endl;
        }
    }

    cout << dp[n][0] << "\n";
}

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