oj.uz

Submission #203606

# Submission time Handle Problem Language Result Execution time Memory
203606 2020-02-21T15:07:38 Z stefdasca Kangaroo (CEOI16_kangaroo) C++14
36 / 100
 2000 ms 63224 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][2][2002][2002];
int main()
{
    cin >> n >> a >> b;
    for(int i = 1; i <= n; ++i)
        if(i != a && i != b)
            dp[0][(a < i)][i - 1 - (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][0][smaller][pos] && !dp[0][1][smaller][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[0][1][smaller][1]);
                    else
                        ans = add(ans, dp[0][0][smaller][1]);
                }
                else
                    for(int relpos = 1; relpos <= sum; ++relpos)
                    {
                        if(pos == relpos)
                            continue;
                        if(relpos <= smaller)
                            dp[1][0][relpos - 1][pos - (relpos < pos)] = add(dp[1][0][relpos - 1][pos - (relpos < pos)],
                                                                                        dp[0][1][smaller][pos]);
                        else
                            dp[1][1][relpos - 1][pos - (relpos < pos)] = add(dp[1][1][relpos - 1][pos - (relpos < pos)],
                                                                                        dp[0][0][smaller][pos]);
                    }
            }
        memcpy(dp[0], dp[1], sizeof(dp[1]));
        memset(dp[1], 0, sizeof(dp[1]));
    }
    cout << ans;
    return 0;
}

Compilation message

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:33:21: warning: unused variable 'bigger' [-Wunused-variable]
                 int bigger = sum - i;
                     ^~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 63096 KB Output is correct
2 Correct 95 ms 63096 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 63096 KB Output is correct
2 Correct 95 ms 63096 KB Output is correct
3 Correct 244 ms 63224 KB Output is correct
4 Correct 362 ms 63096 KB Output is correct
5 Correct 353 ms 63224 KB Output is correct
6 Correct 355 ms 63096 KB Output is correct
7 Correct 341 ms 63224 KB Output is correct
8 Correct 357 ms 63096 KB Output is correct
9 Correct 363 ms 63224 KB Output is correct
10 Correct 362 ms 63096 KB Output is correct
11 Correct 351 ms 63100 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 63096 KB Output is correct
2 Correct 95 ms 63096 KB Output is correct
3 Correct 244 ms 63224 KB Output is correct
4 Correct 362 ms 63096 KB Output is correct
5 Correct 353 ms 63224 KB Output is correct
6 Correct 355 ms 63096 KB Output is correct
7 Correct 341 ms 63224 KB Output is correct
8 Correct 357 ms 63096 KB Output is correct
9 Correct 363 ms 63224 KB Output is correct
10 Correct 362 ms 63096 KB Output is correct
11 Correct 351 ms 63100 KB Output is correct
12 Execution timed out 2090 ms 63096 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 63096 KB Output is correct
2 Correct 95 ms 63096 KB Output is correct
3 Correct 244 ms 63224 KB Output is correct
4 Correct 362 ms 63096 KB Output is correct
5 Correct 353 ms 63224 KB Output is correct
6 Correct 355 ms 63096 KB Output is correct
7 Correct 341 ms 63224 KB Output is correct
8 Correct 357 ms 63096 KB Output is correct
9 Correct 363 ms 63224 KB Output is correct
10 Correct 362 ms 63096 KB Output is correct
11 Correct 351 ms 63100 KB Output is correct
12 Execution timed out 2090 ms 63096 KB Time limit exceeded
13 Halted 0 ms 0 KB -