oj.uz

Submission #236677

# Submission time Handle Problem Language Result Execution time Memory
236677 2020-06-02T19:37:19 Z Sorting Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 2000 ms 63948 KB 
#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.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1536 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1536 KB Output is correct
12 Correct 394 ms 29800 KB Output is correct
13 Correct 224 ms 19448 KB Output is correct
14 Correct 49 ms 3656 KB Output is correct
15 Correct 472 ms 28452 KB Output is correct
16 Correct 24 ms 2176 KB Output is correct
17 Correct 408 ms 30544 KB Output is correct
18 Correct 139 ms 9720 KB Output is correct
19 Correct 410 ms 30964 KB Output is correct
20 Correct 432 ms 31576 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 6 ms 1408 KB Output is correct
5 Correct 5 ms 768 KB Output is correct
6 Correct 6 ms 1792 KB Output is correct
7 Correct 6 ms 1536 KB Output is correct
8 Correct 5 ms 768 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 6 ms 1536 KB Output is correct
12 Correct 394 ms 29800 KB Output is correct
13 Correct 224 ms 19448 KB Output is correct
14 Correct 49 ms 3656 KB Output is correct
15 Correct 472 ms 28452 KB Output is correct
16 Correct 24 ms 2176 KB Output is correct
17 Correct 408 ms 30544 KB Output is correct
18 Correct 139 ms 9720 KB Output is correct
19 Correct 410 ms 30964 KB Output is correct
20 Correct 432 ms 31576 KB Output is correct
21 Execution timed out 2080 ms 63948 KB Time limit exceeded
22 Halted 0 ms 0 KB -