Submission #666541

#	Time	Username	Problem	Language	Result	Execution time	Memory
666541		Arixcrest	Kangaroo (CEOI16_kangaroo)	C++17	100 / 100	29 ms	22988 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pi pair<int,int> 
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define getunique(v) {sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());}
const ll INF = -1;
const int mx = 1e5+5;
const int modulo =1e9+7;
mt19937 mt;
ll dp[2005][2005];

void solve(){
	int n,s,e;
	cin>>n>>s>>e;
	dp[1][1] = 1;
	if(s>e) swap(s,e);
	rep(x,2,n+1){
		rep(y,1,x+1){
			if(dp[x-1][y]==0) continue;
			if(x==s){
				dp[x][y+1] = (dp[x][y+1]+(dp[x-1][y]))%modulo;
				dp[x][y] = (dp[x][y]+(dp[x-1][y]))%modulo;
				continue;
			}
			else if(x==e){
				dp[x][y+1] = (dp[x][y+1]+(dp[x-1][y]))%modulo;
				dp[x][y] = (dp[x][y]+(dp[x-1][y]))%modulo;
				continue;
			}
			if(x<s){
				dp[x][y+1] = (dp[x][y+1]+(dp[x-1][y]*(y+1))%modulo)%modulo;
				dp[x][y-1] = (dp[x][y-1]+(dp[x-1][y]*(y-1))%modulo)%modulo;
			}
			else if(x>s && x<e){
				dp[x][y+1] = (dp[x][y+1]+(dp[x-1][y]*(y+1-1))%modulo)%modulo;
				dp[x][y-1] = (dp[x][y-1]+(dp[x-1][y]*(y-1))%modulo)%modulo;
			}else{
				dp[x][y+1] = (dp[x][y+1]+(dp[x-1][y]*(y+1-2))%modulo)%modulo;
				dp[x][y-1] = (dp[x][y-1]+(dp[x-1][y]*(y-1))%modulo)%modulo;
			}
		}
	}
	// rep(x,0,n+1){
	// 	rep(y,0,n+1){
	// 		cout<<dp[x][y]<<" ";
	// 	}cout<<"\n";
	// }
	cout<<dp[n][1]<<"\n";
}








int main(){
	ios_base ::sync_with_stdio(0), cin.tie(0);
	clock_t start, end;
	start = clock();
	int t = 1;
	// cin >> t;
	// int x=0;
	while (t-->0)
	{
        //cout<<"Case #"<<x<<": ";
		solve();
        // x++;
	}
	end = clock();
	cerr << double(end - start) / double(CLOCKS_PER_SEC) << '\n';
}

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