Submission #96895

#	Time	Username	Problem	Language	Result	Execution time	Memory
96895		Kastanda	캥거루 (CEOI16_kangaroo)	C++11	51 / 100	54 ms	2424 KiB

kangaroo

// I do it for the glory
#include<bits/stdc++.h>
using namespace std;
const int N = 205, Mod = 1e9 + 7;
int dp[2][N][N][2];
int ps[N][N][2];
inline int MOD(int a)
{
    if (a >= Mod) a -= Mod;
    if (a < 0) a += Mod;
    return a;
}
int main()
{
    int n, s, f;
    scanf("%d%d%d", &n, &s, &f);
    dp[0][1][2][0] = dp[0][2][1][1] = 1;
    for (int i = 3; i <= n; i ++)
    {
        int w = i & 1;
        memset(ps, 0, sizeof(ps));
        for (int st = 1; st <= i; st ++)
            for (int fn = 1; fn <= i; fn ++)
            {
                ps[st][fn][0] = MOD(ps[st-1][fn][0] + dp[!w][st][fn][0]);
                ps[st][fn][1] = MOD(ps[st-1][fn][1] + dp[!w][st][fn][1]);
            }
        for (int st = 1; st <= i; st ++)
            for (int fn = st + 1; fn <= i; fn ++)
            {
                dp[w][st][fn][0] = MOD(ps[i-1][fn-1][1] - ps[st-1][fn-1][1]);
                dp[w][st][fn][1] = ps[st-1][fn-1][0];
            }
        for (int fn = 1; fn <= i; fn ++)
            for (int st = fn + 1; st <= i; st ++)
            {
                dp[w][st][fn][0] = dp[w][i - st + 1][i - fn + 1][1];
                dp[w][st][fn][1] = dp[w][i - st + 1][i - fn + 1][0];
            }
    }
    return !printf("%d\n", MOD(dp[n & 1][s][f][0] + dp[n & 1][s][f][1]));
}

Compilation message (stderr)

kangaroo.cpp: In function 'int main()':
kangaroo.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &s, &f);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49