Submission #236677

#	Time	Username	Problem	Language	Result	Execution time	Memory
236677		Sorting	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	2080 ms	63948 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3")

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

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

void fix(int &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;

    for(int left = 0; left <= cf; ++left){
        for(int right = 0; right <= n - cf; ++right){
            for(int side = 0; side <= 1; ++side){
                int cnt = (side ? right : left);

                for(int position = 0; position < cnt; ++position){
                    for(int direction = 0; direction <= 1; ++direction){
                        int &answer = dp[left][right][side][position][direction];

                        if(left == 0 && right == 1){
                            answer = 1;
                            continue;
                        }
                        if(side == 1 && position == 0){
                            answer = 0;
                            continue;
                        }

                        answer = 0;
                        if(!side){
                            if(!direction){
                                for(int new_position = 0; new_position < position; ++new_position){
                                    answer += dp[left - 1][right][0][new_position][1];
                                    fix(answer);
                                }
                            }
                            else{
                                for(int new_position = position; new_position < left - 1; ++new_position){
                                    answer += dp[left - 1][right][0][new_position][0];
                                    fix(answer);
                                }
                                for(int new_position = 0; new_position < right; ++new_position){
                                    answer += dp[left - 1][right][1][new_position][0];
                                    fix(answer);
                                }
                            }
                        }
                        else{
                            if(direction){
                                for(int new_position = position; new_position < right - 1; ++new_position){
                                    answer += dp[left][right - 1][1][new_position][0];
                                    fix(answer);
                                }
                            }
                            else{
                                for(int new_position = 0; new_position < position; ++new_position){
                                    answer += dp[left][right - 1][1][new_position][1];
                                    fix(answer);
                                }
                                for(int new_position = 0; new_position < left; ++new_position){
                                    answer += dp[left][right - 1][0][new_position][1];
                                    fix(answer);
                                }
                            }
                        }

                        //cout << dp[left][right][side][position][direction] << " - " << left << " " << right << " " << side << " " << position << " " << direction << endl;
                    }
                }
            }
        }
    }

    int answer = 0;
    if(cs < cf){
        answer += dp[cf][n - cf][0][cs][0];
        answer += dp[cf][n - cf][0][cs][1];
    }
    else{
        answer += dp[cf][n - cf][1][cs - cf][0];
        answer += dp[cf][n - cf][1][cs - cf][1];
    }

    fix(answer);

    cout << answer << "\n";
}

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