Submission #129937

#	Time	Username	Problem	Language	Result	Execution time	Memory
129937		davitmarg	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	339 ms	266960 KiB

kangaroo

/*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;
}
 
 
/*
 
 
 
 
*/

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