oj.uz

Submission #236673

# Submission time Handle Problem Language Result Execution time Memory
236673 2020-06-02T19:33:12 Z Sorting Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 2000 ms 87576 KB 
#include <bits/stdc++.h>

using namespace std;

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 436 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 436 KB Output is correct
3 Correct 5 ms 512 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 1664 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 5 ms 1408 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 436 KB Output is correct
3 Correct 5 ms 512 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 1664 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 5 ms 1408 KB Output is correct
12 Correct 220 ms 29688 KB Output is correct
13 Correct 124 ms 19448 KB Output is correct
14 Correct 31 ms 3576 KB Output is correct
15 Correct 258 ms 28500 KB Output is correct
16 Correct 19 ms 2304 KB Output is correct
17 Correct 227 ms 30540 KB Output is correct
18 Correct 79 ms 9720 KB Output is correct
19 Correct 226 ms 30880 KB Output is correct
20 Correct 236 ms 31608 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 436 KB Output is correct
3 Correct 5 ms 512 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 1664 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 6 ms 1792 KB Output is correct
10 Correct 5 ms 1280 KB Output is correct
11 Correct 5 ms 1408 KB Output is correct
12 Correct 220 ms 29688 KB Output is correct
13 Correct 124 ms 19448 KB Output is correct
14 Correct 31 ms 3576 KB Output is correct
15 Correct 258 ms 28500 KB Output is correct
16 Correct 19 ms 2304 KB Output is correct
17 Correct 227 ms 30540 KB Output is correct
18 Correct 79 ms 9720 KB Output is correct
19 Correct 226 ms 30880 KB Output is correct
20 Correct 236 ms 31608 KB Output is correct
21 Execution timed out 2085 ms 87576 KB Time limit exceeded
22 Halted 0 ms 0 KB -