oj.uz

답안 #203607

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203607 2020-02-21T15:08:45 Z stefdasca 캥거루 (CEOI16_kangaroo) C++14
51 / 100
 2000 ms 17784 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]);
                    }
            }
        for(int x = 0; x <= 1; ++x)
            for(int q = 0; q <= n; ++q)
                for(int p = 0; p <= n; ++p)
                    dp[0][x][q][p] = dp[1][x][q][p], dp[1][x][q][p] = 0;
    }
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 1020 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 6 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 1020 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 6 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 560 ms 4216 KB Output is correct
13 Correct 329 ms 3960 KB Output is correct
14 Correct 51 ms 4216 KB Output is correct
15 Correct 529 ms 4216 KB Output is correct
16 Correct 66 ms 4216 KB Output is correct
17 Correct 558 ms 4216 KB Output is correct
18 Correct 154 ms 3832 KB Output is correct
19 Correct 549 ms 4088 KB Output is correct
20 Correct 599 ms 4344 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 760 KB Output is correct
4 Correct 6 ms 1016 KB Output is correct
5 Correct 5 ms 1020 KB Output is correct
6 Correct 6 ms 1016 KB Output is correct
7 Correct 6 ms 888 KB Output is correct
8 Correct 5 ms 1016 KB Output is correct
9 Correct 6 ms 1016 KB Output is correct
10 Correct 6 ms 1016 KB Output is correct
11 Correct 6 ms 1016 KB Output is correct
12 Correct 560 ms 4216 KB Output is correct
13 Correct 329 ms 3960 KB Output is correct
14 Correct 51 ms 4216 KB Output is correct
15 Correct 529 ms 4216 KB Output is correct
16 Correct 66 ms 4216 KB Output is correct
17 Correct 558 ms 4216 KB Output is correct
18 Correct 154 ms 3832 KB Output is correct
19 Correct 549 ms 4088 KB Output is correct
20 Correct 599 ms 4344 KB Output is correct
21 Execution timed out 2084 ms 17784 KB Time limit exceeded
22 Halted 0 ms 0 KB -