제출 #129937

#제출 시각아이디문제언어결과실행 시간메모리
129937davitmargKangaroo (CEOI16_kangaroo)C++17
51 / 100
339 ms266960 KiB
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
int n,st,en;
LL dp1[202][202][202],dp0[202][202][202],pr1[202][202][202],pr0[202][202][202];
 
int main()
{
	cin>>n>>st>>en;
   // if(st>en)
//		swap(st,en);
    dp1[2][1][2]=1;
    dp0[2][2][1]=1;
    dp1[2][1][2]=1;
    dp0[2][2][1]=1;
    for(int i=3;i<=n;i++)
	{
        for(int t=1;t<=i;t++)
            for(int s=1;s<=i;s++)
			{
				pr0[i-1][s][t]=pr0[i-1][s-1][t]+dp0[i-1][s][t];
				pr1[i-1][s][t]=pr1[i-1][s-1][t]+dp1[i-1][s][t];
			}
 
        for(int t=1;t<=i;t++)
		{
            for(int s=1;s<=i;s++)
			{
				if(s==t)
					continue;
				dp0[i][s][t]=pr1[i-1][s-1][t-(s<t)];
				dp1[i][s][t]=(pr0[i-1][i][t-(s<t)]-pr0[i-1][s-1][t-(s<t)]+mod);
				dp1[i][s][t]%=mod;
				dp0[i][s][t]%=mod;
				//cout<<"!!0 "<< i <<" "<< s <<" "<< t <<" = "<<dp0[i][s][t]<<endl;
				//cout<<"!!1 "<< i <<" "<< s <<" "<< t <<" = "<<dp1[i][s][t]<<endl;
			}
		}
	}
    cout<<(dp0[n][st][en]+dp1[n][st][en])%mod<<endl;
	return 0;
}
 
 
/*
 
 
 
 
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...