제출 #1335707

#제출 시각아이디문제언어결과실행 시간메모리
1335707developinpop캥거루 (CEOI16_kangaroo)C++20
36 / 100
4 ms1860 KiB
/*
_____________________.
|____________________|   $$\                                                            $$\           $$\        $$\               
|____________________|   $$ |                                                           \__|          $$ |       $$ |              
|____________________| $$$$$$\    $$$$$$\  $$$$$$\  $$$$$$$\   $$$$$$$\        $$$$$$\  $$\  $$$$$$\  $$$$$$$\ $$$$$$\    $$$$$$$\ 
|____________________| \_$$  _|  $$  __$$\ \____$$\ $$  __$$\ $$  _____|      $$  __$$\ $$ |$$  __$$\ $$  __$$\\_$$  _|  $$  _____|
|____________________|   $$ |    $$ |  \__|$$$$$$$ |$$ |  $$ |\$$$$$$\        $$ |  \__|$$ |$$ /  $$ |$$ |  $$ | $$ |    \$$$$$$\  
                         $$ |$$\ $$ |     $$  __$$ |$$ |  $$ | \____$$\       $$ |      $$ |$$ |  $$ |$$ |  $$ | $$ |$$\  \____$$\ 
                         \$$$$  |$$ |     \$$$$$$$ |$$ |  $$ |$$$$$$$  |      $$ |      $$ |\$$$$$$$ |$$ |  $$ | \$$$$  |$$$$$$$  |
            へ   ♡        \____/ \__|      \_______|\__|  \__|\_______/       \__|      \__| \____$$ |\__|  \__|  \____/ \_______/ 
         ૮ - ՛)                                                                             $$\   $$ |    
         / ⁻ ៸|                                                                              \$$$$$$  |   are human rights :3
     乀 (ˍ,ل ل                                                                               \______/ 
 
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
template <typename T>
using ordered_multiset = tree<pair<T, long long>, null_type, 
                      less<pair<T, long long>>, rb_tree_tag, 
                         tree_order_statistics_node_update>;
 
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define ull unsigned long long
#define ld long double
#define inf (ll)2e18+4
#define pb push_back
#define se second
#define fi first
#define endl '\n'
#define mp make_pair
#define pll pair<ll,ll>
#define kth_smallest find_by_order
#define num_of_smaller order_of_key
#define fori(x) for(ll i=0;i<x;i++)
#define forj(y) for(ll j=0;j<y;j++)
#define fork(z) for(ll k=0;k<z;k++)
#define forl(a) for(ll l=0;l<a;l++)
 
#define DEBUG
 
#ifdef DEBUG
#define show(x) cerr<<#x<<" is "<<x<<endl;
#define show2(x,y) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define show3(x,y,z) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<endl;
#define show4(x,y,z,a) cerr<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<" "<<#z<<" is "<<z<<" "<<#a<<" is "<<a<<endl;
#define show_vec(a) for(auto &i:a)cerr<<i<<" ";cerr<<endl;
#define skillissue cerr<<"your code is running\n";
#define getchar_unlocked _getchar_nolock // comment before submission
#else
#define show(x)
#define show2(x,y)
#define show3(x,y,z)
#define show4(x,y,z,a)
#define show_vec(a)
#define skillissue
#endif
 
/*
 
inline int readint() {
    int x=0; char ch=getchar_unlocked(); bool s=1;
    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar_unlocked();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar_unlocked();}
    return s?x:-x;
}
 
*/


const ll mod=1e9+7;
const ll maxn=80+4;
unordered_map<ll,ll>mem[maxn][maxn][2];
ll dp(ll l,ll r,bool las,ll temp){
	if(temp==0 and (l!=0 or r!=0))return 0;
	if(temp==0 and l==0 and r==0)return 1;
	if(mem[l][r][las][temp]==-1)return 0;
	else if(mem[l][r][las][temp]!=0)return mem[l][r][las][temp];
	//show4(l,r,las,temp)
	if(las){
		ll cnt=0;
		for(ll i=1;i<=r;i++){
			cnt = (cnt+dp(l+i-1,r-i,0,temp-i+(ll)(temp<0)))%mod;
		}
		if(cnt==0){
			mem[l][r][las][temp]=-1;
			return 0;
		}else return mem[l][r][las][temp]=cnt%mod;
	}else{
		ll cnt=0;
		for(ll i=1;i<=l;i++){
			cnt = (cnt+dp(l-i,r+i-1,1,temp+i-(ll)(temp>0)))%mod;
		}
		if(cnt==0){
			mem[l][r][las][temp]=-1;
			return 0;
		}else return mem[l][r][las][temp]=cnt%mod;
	}
}

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n,s,e;cin>>n>>s>>e;
	//show2(dp(s-1,n-s,0,e-s),dp(s-1,n-s,1,e-s))
	cout<<(dp(s-1,n-s,0,e-s)+dp(s-1,n-s,1,e-s))%mod;
	
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...