oj.uz

Submission #203603

# Submission time Handle Problem Language Result Execution time Memory
203603 2020-02-21T14:57:23 Z stefdasca Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 678 ms 33144 KB 
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n, a, b;
int add(int a, int b)
{
    int x = a+b;
    if(x >= mod)
        x -= mod;
    if(x < 0)
        x += mod;
    return x;
}
int dp[2][202][202][202];
int main()
{
    cin >> n >> a >> b;
    for(int i = 1; i <= n; ++i)
        if(i != a && i != b)
            dp[(a < i)][i - 1 - (a < i)][n - i - (a > i)][b - (a < b) - (i < b)] = 1;
    if(n == 2)
    {
        cout << 1;
        return 0;
    }
    int ans = 0;
    for(int sum = n-2; sum >= 1; --sum)
    {
        for(int i = 0; i <= sum; ++i)
            for(int pos = 1; pos <= sum; ++pos)
            {
                int smaller = i;
                int bigger = sum - i;
                if(!dp[0][smaller][bigger][pos] && !dp[1][smaller][bigger][pos])
                    continue;
               // cout << sum << '\n';
              //  cout << smaller << " " << bigger << " " << pos << '\n';
              //  cout << dp[0][smaller][bigger][pos] << " " << dp[1][smaller][bigger][pos] << '\n';
                if(sum == 1)
                {
                    if(smaller)
                        ans = add(ans, dp[1][smaller][bigger][1]);
                    else
                        ans = add(ans, dp[0][smaller][bigger][1]);
                }
                else
                    for(int relpos = 1; relpos <= sum; ++relpos)
                    {
                        if(pos == relpos)
                            continue;
                        if(relpos <= smaller)
                            dp[0][relpos - 1][sum - relpos][pos - (relpos < pos)] = add(dp[0][relpos - 1][sum - relpos][pos - (relpos < pos)],
                                                                                        dp[1][smaller][bigger][pos]);
                        else
                            dp[1][relpos - 1][sum - relpos][pos - (relpos < pos)] = add(dp[1][relpos - 1][sum - relpos][pos - (relpos < pos)],
                                                                                        dp[0][smaller][bigger][pos]);
                    }
            }
    }
    cout << ans;
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 6 ms 1656 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 6 ms 1784 KB Output is correct
9 Correct 7 ms 1784 KB Output is correct
10 Correct 6 ms 1784 KB Output is correct
11 Correct 6 ms 1784 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 6 ms 1656 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 6 ms 1784 KB Output is correct
9 Correct 7 ms 1784 KB Output is correct
10 Correct 6 ms 1784 KB Output is correct
11 Correct 6 ms 1784 KB Output is correct
12 Correct 642 ms 32892 KB Output is correct
13 Correct 386 ms 28920 KB Output is correct
14 Correct 59 ms 32632 KB Output is correct
15 Correct 638 ms 33144 KB Output is correct
16 Correct 76 ms 32760 KB Output is correct
17 Correct 655 ms 33096 KB Output is correct
18 Correct 182 ms 26360 KB Output is correct
19 Correct 638 ms 32124 KB Output is correct
20 Correct 678 ms 33084 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 6 ms 1784 KB Output is correct
5 Correct 6 ms 1656 KB Output is correct
6 Correct 6 ms 1656 KB Output is correct
7 Correct 6 ms 1528 KB Output is correct
8 Correct 6 ms 1784 KB Output is correct
9 Correct 7 ms 1784 KB Output is correct
10 Correct 6 ms 1784 KB Output is correct
11 Correct 6 ms 1784 KB Output is correct
12 Correct 642 ms 32892 KB Output is correct
13 Correct 386 ms 28920 KB Output is correct
14 Correct 59 ms 32632 KB Output is correct
15 Correct 638 ms 33144 KB Output is correct
16 Correct 76 ms 32760 KB Output is correct
17 Correct 655 ms 33096 KB Output is correct
18 Correct 182 ms 26360 KB Output is correct
19 Correct 638 ms 32124 KB Output is correct
20 Correct 678 ms 33084 KB Output is correct
21 Runtime error 14 ms 2296 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -