제출 #580517

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
580517		andrei_boaca	캥거루 (CEOI16_kangaroo)	C++14	51 / 100	2083 ms	31840 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;
ifstream fin("kangaroo.in");
ofstream fout("kangaroo.out");
typedef long long ll;
const ll mod=1e9+7;
ll n,cs,cf,dp[2][2005][2005][2],suma[2005][2005][2];
int main()
{
    cin>>n>>cs>>cf;
    dp[0][1][2][1]=1;
    dp[0][2][1][0]=1;
    for(int f=1;f<=2;f++)
        for(int s=1;s<=2;s++)
            for(int j=0;j<=1;j++)
                suma[f][s][j]=(suma[f][s-1][j]+dp[0][s][f][j])%mod;
    for(int i=3;i<=n;i++)
    {
        for(int s=1;s<=i;s++)
            for(int f=1;f<=i;f++)
            {
                dp[1][s][f][0]=0;
                dp[1][s][f][1]=0;
                if(s==f)
                    continue;
                if(s<f)
                {
                    ll x=s-1;
                    ll y=f-s-1;
                    ll z=i-f;
                    dp[1][s][f][0]=suma[x+y+1][x][1];
                    dp[1][s][f][1]=suma[x+y+1][x+y+z+1][0]-suma[x+y+1][x][0];
                    if(dp[1][s][f][1]<0)
                        dp[1][s][f][1]+=mod;
                }
            }
        for(int s=1;s<=i;s++)
            for(int f=1;f<=i;f++)
            {
                if(s==f)
                    continue;
                if(s>f)
                {
                    if(i%2==0)
                    {
                        dp[1][s][f][0]=dp[1][f][s][1];
                        dp[1][s][f][1]=dp[1][f][s][0];
                    }
                    else
                    {
                        dp[1][s][f][0]=dp[1][f][s][0];
                        dp[1][s][f][1]=dp[1][f][s][1];
                    }
                }
            }
        for(int f=1;f<=i;f++)
            for(int s=1;s<=i;s++)
                for(int j=0;j<=1;j++)
                {
                    suma[f][s][j]=(suma[f][s-1][j]+dp[1][s][f][j])%mod;
                    dp[0][s][f][j]=dp[1][s][f][j];
                }
    }
    ll ans=(dp[0][cs][cf][0]+dp[0][cs][cf][1])%mod;
    cout<<ans;
    return 0;
}

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