oj.uz

Submission #236725

# Submission time Handle Problem Language Result Execution time Memory
236725 2020-06-03T06:51:47 Z Sorting Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>

using namespace std;

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

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

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--;
    if(cs > cf)
        swap(cs, cf);

    for(int pos = 0; pos <= n; ++pos){
        for(int group = 0; group <= n; ++group){
            int &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)
                    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){
                    answer += dp[pos - 1][group - 1] * (((group * group % k_Mod - 3 * group + 3) % k_Mod + k_Mod) % k_Mod) % k_Mod;
                    fix(answer);
                }
            }

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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Output isn't correct